黑马程序员技术交流社区
标题:
什么是递归?
[打印本页]
作者:
OK、憨仔
时间:
2014-3-19 22:27
标题:
什么是递归?
帮我解释一下什么是
递归
? 最好能距离说明一下啊
作者:
往事如烟
时间:
2014-3-19 23:14
解释:程序调用自身的编程技巧叫做递归。
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。
递归的三个条件:
边界条件
递归前进段
递归返回段
当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
下面通过两个示例程序来说明:
使用Java代码求5的阶乘。(5的阶乘=5*4*3*2*1)
[java]
package org.wxp.recursion;
/**
* 计算5的阶乘(result = 5*4*3*2*1)
* @author Champion.Wong
*
*
*/
public class Test01 {
public static void main(String[] args) {
System.out.println(f(5));
}
public static int f(int n) {
if (1 == n)
return 1;
else
return n*(n-1);
}
}
此题中,按照递归的三个条件来分析:
(1)边界条件:阶乘,乘到最后一个数,即1的时候,返回1,程序执行到底;
(2)递归前进段:当前的参数不等于1的时候,继续调用自身;
(3)递归返回段:从最大的数开始乘,如果当前参数是5,那么就是5*4,即5*(5-1),即n*(n-1)
使用Java代码求数列:1,1,2,3,5,8......第40位的数
[java]
package org.wxp.recursion;
/**
* 求数列:1,1,2,3,5,8......第40位的数
* @author Champion.Wong
*
*/
public class Test_02_Fibonacci {
public static void main(String[] args) {
System.out.println(f(6));
}
public static int f(int n ) {
if (1== n || 2 == n)
return 1;
else
return f(n-1) + f(n-2);
}
}
此题的突破口在:从第3位数开始,本位数是前两位数的和。要计算第多少位的值,那么就需要将位数作为参数传进方法进行计算。
(1)首先,当位数为1和2时,当前返回的值应该是1;
(2)然后,当位数为3时,返回值应该=2=1+1;
当位数为4时,返回值=3=2+1;
当位数为5时,返回值=5=3+2;
当位数为6时,返回值=8=5+3;
......
(3)由(2)得知,大于等于3的情况下,当前位数(n)的数值=f(n-1)+f(n-2)
心得:有些初学者可能认为递归即是自己调用自己,那岂不是死循环了。对,如果递归写的不合理,那就是死循环了。但是如果写的合理,加上“边界条件”,程序执行到底的时候,会逐层返回。就像我们爬山一样,我们绕着山路爬上一层又一层,如果没有山顶,我们会一直往上爬。但如果到了山顶,就按照上山时候的步骤一层一层的往下爬。
转载的,我感觉比较好理解,原文地址 http://www.2cto.com/kf/201301/181639.html
作者:
青木郎
时间:
2014-3-19 23:31
就是从下往上推
void fee(int n)
{
if(n==1)
reyurn 1;
if(n==2)
return 1;
else
return fee(n-1)+fee(n-2);
}
这个例子就是我们只知道n=1,h=2是的值 ,想求你》2时;就要向下递归,
接入求fee(10
fee(10)=fee(9)+fee(8);
而fee(9)=fee(8)+fee(7)
……
以此类推知道fee(3)=fee(2)+fee(1);
在慢慢往上返回去就最终结果,这种方法就叫递归
作者:
linweiwen
时间:
2014-3-19 23:32
递归就像爬楼梯一样,每一层的阶梯看似重复,但最终却能到达楼顶。
它是不断调用自己的方法,将大问题化为小问题的编程技巧。
/**
* 计算5的阶乘(result = 5*4*3*2*1)
*
*/
public class Test01 {
public static void main(String[] args) {
System.out.println(f(5));
}
public static int f(int n) {
if (1 == n)
return 1;
else
return n*(n-1);
}
}
复制代码
这面这题就是不断通过调用f()这个方法,最终达到计算5的阶乘的目的。
上面这题比较简单,再看一题:
Q:求2/1+3/2+5/3+8/5...前20项
这题通过找规律,可以知道“前一个数的分子,是后一个数的分母”,
“前一个数的分子、分母的和,是后一个数的分子” ,“前20项”就是题目设定的递归范围。
就是这样通过找规律,找出递归条件,写出那个方法:
public class TestSum {
public static void main(String args[]) {
System.out.println(getSum(2,1,20));
}
public static double getSum(double molecular ,double denominator,int limit){
if(limit ==1){
return molecular/denominator;
}else{
double sum = molecular/denominator;
double tmp1 = molecular;
double tmp2 = molecular+denominator;
limit--;
return sum += getSum(tmp2,tmp1,limit);
}
}
}
复制代码
作者:
mohuancaizi
时间:
2014-3-20 00:35
递归:就是函数自身调用自身。
什么时候用递归呢?
当一个功能被重复使用,而每一次使用该功能时的参数不确定,都由上次的功能元素结果来确定。
简单说:功能内部又用到该功能,但是传递的参数值不确定。(每次功能参与运算的未知内容不确定)。
递归的注意事项:
1:一定要定义递归的条件。
2:递归的次数不要过多。容易出现 StackOverflowError 栈内存溢出错误。
其实递归就是在栈内存中不断的加载同一个函数。
作者:
漫天沙飞
时间:
2014-3-20 12:31
所谓递归,是指程序调用自身,当然,递归不会无休止地调用下去,它必然有一个出口,当满足条件时程序也就结束了,不然的话,那就是死循环了。
public class Recursion{
//递归方法sum,求1+2+...+100 的求和
public static int sum(int num){
if(num > 0){
return num + sum(num-1); //调用递归方法
}else{
return0; //当num=0时,循环结束
}
}
//主函数main
public static void main(String [] args){
System.out.println(sum(100));//求和
}
}
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2