老C看·递归
想必，大家学任何一门程序语言学到函数那一章最后面肯定要讲到"递归"这个东西。（没讲？）没讲是出书的||老师不负责任。
然后呢，一般而言大多数人会在这里卡壳。除非是计算机＋数学天才。
然而像老C这么笨的，根本没天赋的肯定晕在了一道题上：用递归求阶乘。
通常，书上会给出例程：
long factorial(int n)
{
if(n == 1)
return 1;
else
return n * factorial(n - 1);
}
然后呢，如果你学得认真。早就用循环解决了这样的问题：
long normalfact(int n)
{
long mutisum = 1;
int i;
for (i = 1; i <= n; i++)
{
mutisum *= i;
}
return mutisum;
//当然哦，我没有对定义域进行判断。
}
等看到了递归这代码，第一反应：噫！这满简洁的！第二反应：我艹！它怎么实现的？
好了，先不管那么多。我们知道所谓函数递归就是，函数自己调用自己。（在函数体内拥有1个或1个以上对于自己本身的调用）
我们先来做几道题好了。
一、写个函数，求1加到任意正整数的和？（就是：1+2+3+4+...+n-1+n 咯）
先不用递归，代码如下：
int normal_sum1tox(int x)
{
int i;
int sum = 0;
for (i = 1; i <= x; i++)
{
sum += i;
}
return sum;
}
这个容易理解。我们现在用一个递归（就是自个儿调用自个儿）：
int sum1tox(int x) //This x signs the end of sequence
{
static int i = 0;
static int s = 0;
if (i < x)
{
i++;
s+=i;
sum1tox(x);
}
return s;
}
我们来看，原理是一样的。哪里不同？循环没了。
逐步分析之：
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了),看大家能不能一下子就理解:
int foo(int n)
{
static int sum = 0;
if (n > 0)
{
sum += n--;
foo(n);
}
return sum;
}
我们深究一下发现，这递归不就相当于goto语句？！你tm逗我？
我们趁热打铁继续来一道题：
二、写个递归函数，求x加到y的值，x,y属于正整数，步长为1.（就是sigma (s=x to y) ,(s) 的值）
int sumx2y(int x, int y)
{
static int s = 0;
if (x <= y)
{
s+=x;
x++;
sumx2y(x, y);
}
return s;
}
同样我们逐个分析。
1.函数头，参数x表示数列首项，y表示末项。公差默认为1.
3.s记录数列各项之和。
4.判断累加器是否到达条件？
6.没到末项？数列之和累加。
7.首项加上步长（1）。
8.递归实现。注意了，此时再去运行函数自个儿，首项已变（加了步长）。
10.返回s的值即为所求答案。
这道例题一出，想必是激起公愤，老C你硬生生把多么精妙的递归说成了goto。
然而goto为大多数“不得要领的”面向过程死党所不齿。
为了缓和气氛，避免公开游行示威。我决定来个“不是goto的递归”，给自己一个台阶下。
三、递归求fibonaccin数列的第n项。
long fibonaccin2nd(int n) //base 1
{
if (n == 0) return 0;
if (n == 1) return 1;
return fibonaccin2nd(n - 2) + fibonaccin2nd(n - 1);
}
然而老C要说这个递归写得不是最好的。
因为这玩意效率太差了。
那么我们使用一个静态变量作为计数器，来求此函数计算斐波那契数列时的调用次数。
修改后代码如下：
#include <stdio.h>
long fibonaccin2nd(int n) //base 1
{
static int c = 0; printf("%d\n", ++c);
if (n == 0) return 0;
if (n == 1) return 1;
return fibonaccin2nd(n - 2) + fibonaccin2nd(n - 1);
}
int main(int argc, const char * argv[])
{
printf("=%d\n", fibonaccin2nd(4));
}
运行结果如下：
1
2
3
4
5
6
7
8
9
=3
Program ended with exit code: 0
这时候老C写一个“goto版递归”同样求fb数列。
long fibonaccin(int n) //base 0
{
static long a = 1;
static long b = 1;
static inti = 1;
static int c = 0; printf("%d\n", ++c);
if (i < n / 2)
{
a+=b;
b+=a;
i++;
fibonaccin(n);
}
if (n % 2)
return b;
else
return a;
}
代码多了好多哦。然而我们用同样的main函数启动goto版函数，得到结果如下：
这里稍微注意一下，goto版斐波 0是第一项，那么要求得3，就得入参5.
1
2
=3
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.计算之，
对于数值则直接给出答案。
答案代码回复后可见：
**** Hidden Message *****
声明：全部代码均在Plain ANSI C，Xcode7.2／Gcc － OSX EI Cpt平台测试无误。
文章版权所有 技术宅的结界 2015
页:
[1]