老C看·递归

cyycoish

想必，大家学任何一门程序语言学到函数那一章最后面肯定要讲到"递归"这个东西。
（没讲？）没讲是出书的||老师不负责任。
然后呢，一般而言大多数人会在这里卡壳。除非是计算机＋数学天才。
然而像老C这么笨的，根本没天赋的肯定晕在了一道题上：用递归求阶乘。
通常，书上会给出例程：

1. long factorial(int n)
   
2. {
   
3.     if(n == 1)
   
4.         return 1;
   
5.     else
   
6.         return n * factorial(n - 1);
   
7. }

复制代码

然后呢，如果你学得认真。早就用循环解决了这样的问题：

1. long normalfact(int n)
   
2. {
   
3.     long mutisum = 1;
   
4.     int i;
   
5.     for (i = 1; i <= n; i++)
   
6.     {
   
7.         mutisum *= i;
   
8.     }
   
9.     return mutisum;
   
10.     //当然哦，我没有对定义域进行判断。
    
11. }

复制代码

等看到了递归这代码，第一反应：噫！这满简洁的！第二反应：我艹！它怎么实现的？
好了，先不管那么多。我们知道所谓函数递归就是，函数自己调用自己。（在函数体内拥有1个或1个以上对于自己本身的调用）
我们先来做几道题好了。
一、写个函数，求1加到任意正整数的和？（就是：1+2+3+4+...+n-1+n 咯）
先不用递归，代码如下：

1. int normal_sum1tox(int x)
   
2. {
   
3.     int i;
   
4.     int sum = 0;
   
5.     for (i = 1; i <= x; i++)
   
6.     {
   
7.         sum += i;
   
8.     }
   
9.     return sum;
   
10. }

复制代码

这个容易理解。我们现在用一个递归（就是自个儿调用自个儿）：

1. int sum1tox(int x) //This x signs the end of sequence
   
2. {
   
3.     static int i = 0;
   
4.     static int s = 0;
   
5.     if (i < x)
   
6.     {
   
7.         i++;
   
8.         s+=i;
   
9.         sum1tox(x);
   
10.     }
    
11.     return s;
    
12. }

复制代码

我们来看，原理是一样的。哪里不同？循环没了。
逐步分析之：
1.函数头，不多说，参数表示末值。
2.大括号。还要我说嘛？
3.静态类型变量i作为累加器之用。
4.静态类型变量s存放数列之和。
为啥s和i都是静态类型变量？等下再说。
5.判断i到没到末值－1
7.8.没到，累加器＋＋，数列之和累加。
9.好了，前面说没到末值－1对吧？然后接着s，i累加完毕了。那么返回去再调用一次自己，又回到了1.函数头处。
  然后呢，如果s，i不是静态类型变量，i，s就被初屎化清空掉了。导致i永远累加不成功，s也永远加不上去。而此时
判断一直判条件符合，最终导致死循环，崩栈了。。。
  然后我们集中精力看实现递归的那一句，就是第9句。x是数列末值，此时被原封不动地代了进去。下一次判断还是x，
保证了结果无误。
再来一个更简的sum1tox(函数名称我写作foo了),看大家能不能一下子就理解:

1. int foo(int n)
   
2. {
   
3.     static int sum = 0;
   
4.     if (n > 0)
   
5.     {
   
6.         sum += n--;
   
7.         foo(n);
   
8.     }
   
9.     return sum;
   
10. }

复制代码

  我们深究一下发现，这递归不就相当于goto语句？！你tm逗我？
我们趁热打铁继续来一道题：
二、写个递归函数，求x加到y的值，x,y属于正整数，步长为1.（就是sigma (s=x to y) ,(s) 的值）

1. int sumx2y(int x, int y)
   
2. {
   
3.     static int s = 0;
   
4.     if (x <= y)
   
5.     {
   
6.         s+=x;
   
7.         x++;
   
8.         sumx2y(x, y);
   
9.     }
   
10.     return s;
    
11. }

复制代码

同样我们逐个分析。
1.函数头，参数x表示数列首项，y表示末项。公差默认为1.
3.s记录数列各项之和。
4.判断累加器是否到达条件？
6.没到末项？数列之和累加。
7.首项加上步长（1）。
8.递归实现。注意了，此时再去运行函数自个儿，首项已变（加了步长）。
10.返回s的值即为所求答案。
这道例题一出，想必是激起公愤，老C你硬生生把多么精妙的递归说成了goto。
然而goto为大多数“不得要领的”面向过程死党所不齿。
为了缓和气氛，避免公开游行示威。我决定来个“不是goto的递归”，给自己一个台阶下。
三、递归求fibonaccin数列的第n项。

1. long fibonaccin2nd(int n) //base 1
   
2. {
   
3.     if (n == 0) return 0;
   
4.     if (n == 1) return 1;
   
5.     return fibonaccin2nd(n - 2) + fibonaccin2nd(n - 1);
   
6. }

复制代码

然而老C要说这个递归写得不是最好的。
因为这玩意效率太差了。
那么我们使用一个静态变量作为计数器，来求此函数计算斐波那契数列时的调用次数。
修改后代码如下：

1. #include <stdio.h>
   
2. 
   
3. long fibonaccin2nd(int n) //base 1
   
4. {
   
5.     static int c = 0; printf("%d\n", ++c);
   
6.     if (n == 0) return 0;
   
7.     if (n == 1) return 1;
   
8.     return fibonaccin2nd(n - 2) + fibonaccin2nd(n - 1);
   
9. }
   
10. 
    
11. int main(int argc, const char * argv[])
    
12. {
    
13.     printf("=%d\n", fibonaccin2nd(4));
    
14. }
    

复制代码

运行结果如下：

1. 
   
2. 1
   
3. 2
   
4. 3
   
5. 4
   
6. 5
   
7. 6
   
8. 7
   
9. 8
   
10. 9
    
11. =3
    
12. Program ended with exit code: 0

复制代码

这时候老C写一个“goto版递归”同样求fb数列。

1. long fibonaccin(int n) //base 0
   
2. {
   
3.     static long a = 1;
   
4.     static long b = 1;
   
5.     static int  i = 1;
   
6.     static int c = 0; printf("%d\n", ++c);
   
7.     if (i < n / 2)
   
8.     {
   
9.         a+=b;
   
10.         b+=a;
    
11.         i++;
    
12.         fibonaccin(n);
    
13.     }
    
14.     if (n % 2)
    
15.         return b;
    
16.     else
    
17.         return a;
    
18. }

复制代码

代码多了好多哦。然而我们用同样的main函数启动goto版函数，得到结果如下：
这里稍微注意一下，goto版斐波 0是第一项，那么要求得3，就得入参5.

1. 
   
2. 1
   
3. 2
   
4. =3
   
5. Program ended with exit code: 0

复制代码

什么鬼！差距如此之大令编译器咂舌。
为了探寻不是goto的递归到底做了什么，我们回到那第一个求阶乘的函数。

我们知道编译器翻译函数的常规形式如下：
入口处理代码＋函数体＋出口处理代码
其中：入口处理代码关乎函数进参和调用，其形式如下：
1.函数名称标号
2.分配栈帧代码
3.保存各种参数（逃逸参数入栈帧，非逃逸参数入临时寄存器）
4.存储“被调函数”的保护寄存器。
＋函数体
函数体后的出口代码是：
1.处理返回值指令
2.恢复保护寄存器
3.释放栈帧
4.jmp到返回地址

我们每次调用一个函数，无论被调者是不是自己（是不是递归函数）都要进行以上的操作。
如果函数自个儿调用了自个儿，实际的处理情况是每调用一次，内部变量都成为逃逸参数
逃逸参数全部根据栈帧入栈。然后栈帧指向的栈每调用一次就会增大，直到执行函数出口代码
栈帧所指之栈被不断销毁。
所以用一些说明性文字说明递归式阶乘函数原理：
(fact 5)
(*5     fact 4)
(*5     *4     (fact 3))
(*5     *4     *3      (fact 2))
(*5     *4     *3      *2      (fact 1))
(*5     (*4    (*3     (*2      1))))
(*5     (*4    (*3     2)))
(*5     (*4    6))
(*5     24)
(120)
ret
所以我们可以解释为什么 fibonaccin2nd 函数工作栈庞大得吓人。
是事实，老C测试fibonaccin2nd(45)的时候着实烧了一把cpu：

然而fibonaccin(45)函数还没等老C进行能耗报告的截图，结果已经出来了:
=701408733

好了，我们现在对goto版递归函数做个“正名”。
我们仔细观察sum1tox、sumx2y、fibonaccin函数
会发现在调用自己实现递归后并未做任何其他计算。
拿fibonaccin和fibonaccin2nd函数来说
fibonaccin函数实现递归通过此条语句：fibonaccin(n);
fibonaccin2nd函数实现递归则通过这条语句：return fibonaccin2nd(n - 2) + fibonaccin2nd(n - 1);
也就是说fibonaccin2nd调用自身一次后并未结束函数体处理，而是又来了一次调用。
在看factorial函数：
factorial通过执行语句“return n * factorial(n - 1);”实现递归。
分析该语句：return n * factorial(n - 1);相当于return factorial(n - 1) ＊ n;（乘法交换律）
说明调用完自身后，factorial又进行了乘法处理。

我们叫上边实现递归后不做任何操作的，形如“goto”形式的调用为 “尾递归”。

那么尾递归可有用啦，在函数式编程当中，根本不存在流程控制语句。循环的实现全靠函数的尾递归。

不管是尾递归还是非尾递归，递归思想在程序设计当中都是相当重要的。
接下来我们通过一个“大作业”来复习递归。

四、使用递归设计简单的带括号的算数表达式处理系统。
要求：
1.可以计算＋－＊／乘方(^)要求有优先级
2.可以计算括号（）
3.可以计算小数，但是不要求设计科学计数法表示的数值。
例如我输入12*（3.5+6）
输出114.00000

接下来我们来一起做这道题：
我不想扯进去很多编译原理语法分析的事情，所以，我们可以这样来看这个处理过程：
如果我们拿到一个非常复杂的甚至带有括号的四则运算，处理流程如下：
1.有括号先算括号里边的。
2.对于括号里边的，我们将表达式都看作＋－两个基础运算拼接而成的式子：
????+????或者????-????
3.而对于????我们看成高一级运算＊或者／两个运算拼接而成的式子：
XXXX*XXXX或者XXXX/XXXX
4.对于XXXX我们分解为AAAA^BBBB
5.对于BBBB利用递归的性质，我们又能分解为CCCC^DDDD......
6.最后的值，不是（????）就是一个具体数值。对于(????)我们使用2.计算之，
对于数值则直接给出答案。

答案代码回复后可见：

游客，如果您要查看本帖隐藏内容请回复

声明：全部代码均在Plain ANSI C，Xcode7.2／Gcc － OSX EI Cpt平台测试无误。
文章版权所有 技术宅的结界 2015