重识递归

递归算法想必大家都已经非常熟悉了，这一次主要也不是教大家怎么使用递归的，在这点上想必有更多的大师在那，小生就不在这献丑了^-^。这次主要是给大家讲解一些我们在使用递归算法时可能没有考虑到的一些问题，在此之前，先看看下面的一个算法：

public long sum(int n){

              if(n==1){

                     return 1;

              }

              else

                     return sum(n-1)+n;

}

不用我说，想必大家也已经知道，这是一个用递归定义的求和算法，在语法结构上没有错误，反复测试也没有问题，但是如果你向这个式子中输入20000或者更大的数字时，你会发现，程序报错了，不是超出长整形的最大范围，因为1到20000的和才200010000，没有超过长整形的最大值。那么是什么呢？运行一下你会发现，是溢出栈空间，那这是为什么呢？教科书上一般并没有讲到这个问题。这是由于：

递归的实现，需要记录一些调用过程以跟踪挂起的递归调用，对于一条足够长的递归链，计算机会耗尽内存来记录递归调用，当它超出的时候，计算机就再也没有内存来记录递归链了。

很明显，不同的计算机内存空间是不一样的，那么他们可以记录的递归链的长度也不一样，我的计算机的记录递归链的最大长度为10464，你也可以试一下自己的。

其实这样的问题要解决也很简单，因为它可以用简单循环来实现，而且既然计算机要记录递归链，那么相对于简单循环来说，递归定义的算法，肯定要稍微耗时一点，不过相对于现代计算机这么快的计算速度，这点时间差异是可以忽略不计的，不过通过上例我们也大概知道了什么时候要少用递归，我们一般也默认为：如果可以用简单循环解决的问题尽量不要用递归。

再看一个大家同样非常熟悉的例子：Fibonacci数，它的定义规则是，从第三个数开始，任意一个数是前两个数字之和，从定义规则中就不难看出，这是一个通过递归定义的数，那么这样的数用递归算法来实现自然也在情理之中了，如下：

public long fibonacci(int n){

              if(n<=2){

                     return 1;

              }

              else

                     return fibonacci(n-1)+fibonacci(n-2);

}

       向其中输入一个100，然后我想你就可以先去喝杯茶了，回来之后你会发现，程序还在运行，而实际上，我们要计算出Fibonacci的第一百个数只要进行99次加法!这对于计算机来说是相当轻松的，但是为什么会出现这种局面了，原因在于：

       这个算法执行了冗余的计算，为了计算fibonacci(n),就要计算fibonacci(n-1)和fibonacci(n-2)，而实际上，在计算fibonacci(n-1)的过程中就已经计算过了fibonacci(n-2)，因此对fibonacci(n-2)的再次调用其实是多此一举的，数值越大，这个情况就会越遭，对于n=40,F40=102334155，而总的递归次数却超过了300000000次，所以为了保证递归算法的执行效率，我们一定注意一条复利原则：永远不要在不同的递归中重复执行解决同一问题实例的工作。

       递归在实际的操作中运用非常广泛，不过我们在使用的时候也要注意场合，考虑程序的执行速度，以后再慢慢的跟大家一起探讨递归的巧妙用处。

评论

6 楼 dt_flys 2013-05-02  

qswdit 写道

没看懂  为什么    return fibonacci(ret, ret, a);    而不是调用本身！

不好意思，写错了，应该是fibonacci_iter(ret, ret, a);

5 楼 qswdit 2013-05-02  

没看懂  为什么    return fibonacci(ret, ret, a);    而不是调用本身！

4 楼 cq520 2013-05-01  

dt_flys 写道

你用的是树形递归，可以转换成尾递归，比如：

public long fibonacci_iter(long ret, long a, long b, int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    ret = a + b;
    return fibonacci(ret, ret, a);
}

public long fibonacci(int n) {
    return fibonacci(1, 1, n);
}

即使是没有尾递归优化的语言也比树形递归要节约一般的资源， 不过可能你可能觉得代码还没for循环来的清晰。

之前没了解过尾递归，感谢提出

3 楼 dt_flys 2013-04-30  

dt_flys 写道

上面我代码写错了
应该是

public long fibonacci_iter(long ret, long a, long b, int n) {  
    if (n == 1 || n == 2) {  
        return ret;  
    }  
    ret = a + b;  
    return fibonacci(ret, ret, a);  
}  
  
public long fibonacci(int n) {  
    return fibonacci(1, 1, n);  
}  

public long fibonacci_iter(long ret, long a, long b, int n) {  
    if (n == 1 || n == 2) {  
        return ret;  
    }  
    ret = a + b;  
    return fibonacci(ret, ret, a);  
}  
  
public long fibonacci(int n) {  
    return fibonacci_iter(1, 1, n);  
}  

[

2 楼 dt_flys 2013-04-30  

上面我代码写错了
应该是

public long fibonacci_iter(long ret, long a, long b, int n) {  
    if (n == 1 || n == 2) {  
        return ret;  
    }  
    ret = a + b;  
    return fibonacci(ret, ret, a);  
}  
  
public long fibonacci(int n) {  
    return fibonacci(1, 1, n);  
}  

1 楼 dt_flys 2013-04-30  

你用的是树形递归，可以转换成尾递归，比如：

public long fibonacci_iter(long ret, long a, long b, int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    ret = a + b;
    return fibonacci(ret, ret, a);
}

public long fibonacci(int n) {
    return fibonacci(1, 1, n);
}

即使是没有尾递归优化的语言也比树形递归要节约一般的资源， 不过可能你可能觉得代码还没for循环来的清晰。