递归的原理
一个函数调用其本身，此调用过程为递归（recursion）。
递归的使用
举个栗子：
/*用来测试UpAndDown函数的驱动程序*/
#include <stdio.h>
void UpAndDown (int);
int main(void)
{
UpAndDown(1);
return 0;
}
void UpAndDown (int n)
{
printf("Level %d: n location %p\n" , n, &n);
if (n < 5)
UpAndDown(n+1);
printf("LEVEL %d: n location %p\n" , n, &n);
}
输出如下：
递归的基本原理
每级递归都使用其私有变量（如例子中的n）
每次函数调用都返回前一级（调用他那级）递归
递归函数中，位于递归调用前的语句和各级被调函数具有相同执行顺序
递归函数中，位于递归调用后的语句和各级被调函数具有相反执行顺序
每级递归会从头执行而不是复制其函数代码，所以一般可代替循环语句。
递归函数必须包含可以终止递归调用的语句（如if）。
尾递归
最简单的递归形式。
把递归调用语句放在函数结尾（return语句之前）。
举个栗子：
计算n的阶乘
long fact (int n) // 使用循环计算阶乘，占内存少，执行快
{
long ans;
for(ans = 1; n>1; n--)
ans *= n;
return ans;
}
long rfact (int n) // 使用递归计算阶乘，仅作尾递归展示、入门
｛
long ans;
if(n > 0)
ans = n * rfact(n-1);
else
ans = 1; //1.零的阶乘；2.结束递归。
return ans;
｝递归和反向计算
将一个整数转换成二进制形式。
void ToBinary (unsigned long n) // 简单须存数组版递归
{
int r;
r = n % 2;
if(n >= 2)
ToBinary(n / 2);
putchar('0' + r); //or: putchar(r ? '1' : '0')
return;
}递归的优缺点
- 优点
- 算法简单
- 缺点
- 占内存，难于阅读和维护
举个栗子：斐波那契数列：第一、二个数字都是1，而后续的每个数字是其前两个数字之和。1、1、2、3、5、8、13……
long Fibonacci (int n)
{
if(n > 2)
return Fibonacci(n-1) + Fibonacci(n-2);
else
return 1;
}双重递归。
致命弱点：每级调用变量数以指数递增！
Something interesting …
main( )也可以被自身递归调用或其他函数调用，尽管用得少。
