栈非常重要的一个应用就是在程序设计语言中用来实现递归。递归是指在定义自身的同时又出现了对自身的引用。如果一个函数在其定义体内直接调用自己，则称为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其他函数间接调用自己，则称为间接递归函数。许多数学函数是递归定义的，如二阶斐波那契数列定义和阿克曼函数定义
// 已知二阶fibonacci数列:fib(n)=0,若n=0；fib(n)=1,若n=1；fib(n)=fib(n-1)+fib(n-2),其他情况。定义递归函数求fib(n).
int fib(int n)
{
if(n==0)return 0;
else if(n==1)return 1;
else return fib(n-1)+fib(n-2);
}
-
使用递归算法的前提有一下两个:- 原问题可以层层分解为类似的子问题，且子问题比原问题的规模更小。
- 规模最小的子问题具有直接解。
-
设计递归算法的原则是用自身的简单情况来定义自身。设计递归算法的方法如下:- 寻找分解方法：将原问题转化为子问题求解。例如,n! = n(n-1)!
- 设计递归出口:根据规模最小的子问题确定递归终止条件。例如求解n!,当n = 1时，n! = 1
int f(int n)
{
if (n == 0) return (1);
else
return (n * f*(n - 1));
}
