首页 > 代码库 > 尾递归与普通递归

尾递归与普通递归

2024-07-07 00:12:01   233人阅读

　　这篇文章总结尾递归，普通递归的区别，以及使用递归时需要注意的问题。

　　

　　1. 递归定义

　　递归有四条基本准则，摘抄自艾伦韦斯的《数据结构与算法分析——C语言描述》。

　　1）基准情形：可以理解为无须递归就可以解出的结果，或者说是递归的最终到达点，或者说是初始条件。

　　2）不断推进：不断的循环，直到达到基准情形。

　　3）设计法则：所有的递归调用能正常运行。

　　4）合成效益法则：求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的事情。

　　

　　下面给出例子来说明四条准则。

　　1）如下就没有初始条件，或者说是结束条件，递归会运行到越界或者栈溢出。

1 void 
2 printList(pListNode head)
3 {
4     std::cout << head->value;
5     printList(head->next);        
6 }

　　2）如下就没有满足“不断推进”，Bad(2)会陷入死循环。

1 int 
2 Bad(unsigned int n)
3 {
4     if (n == 0)　　// 初始条件
5         return 0;
6     else 
7     return Bad( n / 3 + 1) + n - 1;
8 }

　　3）如下设计的递归调用就不能正常运行，当N = 2时会造成无限循环。

 1 long int 
 2 Pow(long int X, unsigned int N)
 3 {
 4     if (N == 0)
 5         return 1;
 6         
 7     if (N == 1)
 8     　　return X;
 9         
10     if (isEven(N))
11     　　return Pow(Pow(X,2), N/2);
12         
13     else
14     　　return Pow(X * X, N/2) * X;
15 }

　　4）如下设计的递归调用不满足“合成设计法则”，第三个if里面，对N/2情况下进行了重复的递归调用。

 1 long int 
 2 Pow(long int X, unsigned int N)
 3 {
 4     if (N == 0)
 5         return 1;
 6         
 7     if (N == 1)
 8     　　return X;
 9         
10     if (isEven(N))
11     　　return Pow(X, N/2) * Pow(X, N/2);
12         
13     else
14     　　return Pow(X * X, N/2) * X;
15 }

　　正确的设计为

 1 long int 
 2 Pow(long int X, unsigned int N)
 3 {
 4     if (N == 0)
 5     　　return 1;
 6         
 7     if (N == 1)
 8     　　return X;
 9         
10     if (isEven(N))
11     　　return Pow(X * X, N/2);
12         
13     else
14     　　return Pow(X * X, N/2) * X; // return Pow(X, N-1) * X  is also right!
15 }

　　以及如下：

1 long int
2 Fib(int N)
3 {
4     if (N <= 1)
5     　　return 1;
6     else 
7     　　return Fib(N-1) + Fib(N-2);
8 }

　

　　2. 尾递归

　　一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归，是递归的一种特殊情形。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

　　尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧——而是更新它，如同迭代一般。尾递归因而具有两个特征：

  • 调用自身函数(Self-called)；
  • 计算仅占用常量栈空间(Stack Space)。

　　而形式上只要是最后一个return语句返回的是一个完整函数，它就是尾递归。

　　更直接一点，引用网上别人的说法：一个对自身的递归尾调用，就是尾递归。

 

　　比如（python表示），这是一个常规递归，因为返回的最后是一个加运算的结果，而不是rescum函数本身，

1 def recsum(x):
2   if x == 1:
3     return x
4   else:
5     return x + recsum(x - 1)

　　这个运行时，以X = 5为例，堆栈的调用情况是如下，组成了一种经典的先增长到顶峰，然后又回落的结构，而且每一层的栈空间都被开辟了。

 1 recsum(5)
 2 5 + recsum(4)
 3 5 + (4 + recsum(3))
 4 5 + (4 + (3 + recsum(2)))
 5 5 + (4 + (3 + (2 + recsum(1))))
 6 5 + (4 + (3 + (2 + 1)))
 7 5 + (4 + (3 + 3))
 8 5 + (4 + 6)
 9 5 + 10
10 15

　　如果将其改为如下，则为尾递归。因为其返回的是tailrescum函数本身返回值。

1 def tailrecsum(x, running_total=0):
2   if x == 0:
3     return running_total
4   else:
5     return tailrecsum(x - 1, running_total + x)

　　这种情况下，编译器会进行优化，保证栈空间只是重复写入，而不会每次调用，每次开辟，每次增长，如下。

1 tailrecsum(5, 0) 
2 tailrecsum(4, 5) 
3 tailrecsum(3, 9)
4 tailrecsum(2, 12) 
5 tailrecsum(1, 14) 
6 tailrecsum(0, 15) 
7 15

　　其效果其实和循环（递推）等一致，如下

1 for i in range(6):
2   sum += i

　　再举一例，下面第一个函数不是尾递归，而第二个是，因为第一个返回的是加法结果，第二个返回对自身的尾调用（最后执行语句对函数的调用）。

 1 int 
 2 fact(int n)
 3 {
 4     if (n < 0)
 5         return 0;
 6     else if (n == 0)
 7         return 1;
 8     else if (n == 1)
 9         return 1;
10     else 
11         return n * fact(n - 1);
12 }
13 
14 int 
15 facttail(int n, int a)
16 {
17     if (n < 0)
18         return 0;
19     else if (n == 0)
20         return 1;
21     else if (n == 1)
22         return a;
23     else 
24         return facttail(n - 1, n * a);
25 }

　　

　　3. 尾递归的使用

　　一般情况下，可以尾递归的可以用循环或者递推来代替，当然尾递归的好处是代码更直接，容易理解。现在的编译器可以将尾递归优化为循环的效果，不过如果发现自己写的递归时一种尾递归的方式，可以考虑用循环写，或者用是否可以变成尾递归的思路去考察自己写的递归是否不满足递归的第四个法则“合成效益法则”，出现时间和空间的浪费，可以借此对优化代码提供帮助。

 

 

 

　　

　　

　　


联系
我们