递归

• 栈非常重要的一个应用就是在程序设计语言中用来实现递归。递归是指在定义自身的同时又出现了对自身的引用。如果一个函数在其定义体内直接调用自己，则称为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其他函数间接调用自己，则称为间接递归函数。

• 许多数学函数是递归定义的，如二阶斐波那契数列定义和阿克曼函数定义

// 已知二阶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));
}