1.4.2 递归设计

递归（Recursion）也是实现重复性计算的一种方法，是指一个过程或函数在定义中直接或间接调用自身的一种方法。递归设计的关键在于找出递归关系（方程）和递归终止（边界）条件。递归关系就是使问题向边界条件转化的规则。一般而言，递归关系必须能使问题越来越简单，规模越来越小。递归终止条件就是所描述问题最简单的、可解的情况，不需要再继续递归或推导下去。

用递归解题通常有三个步骤。

（1）分析问题找到递归关系：找出大规模问题与小规模问题的关系，以便通过递归使问题规模变小。

（2）设置终止条件控制递归：通过停止条件的设置，找出可解的最小规模问题。

（3）设计函数确定数据传递方式。

【例1-5】 运用递归方式设计求解斐波那契数列（Fibonacci sequence）的第n项的值。

计算模型

斐波那契数列求解是非常经典的算法，它的推导公式就展现了递归的终止条件和递归方程，如下式所示：

其中，式（1-15）是递归方程，式（1-14）是终止条件。

算法分析

依据计算模型，容易得知，求第n项的值需要计算n-2次，所以主体算法计算次数约为f(n)=n-2。

算法实现

int fcc(int n)
{
      int t;
      if (n==1||n==2)
            {
            return 1;
           }
      else
      return fcc(n - 1)+fcc(n - 2);
}
void main()
{
      int n;
      printf("input n:");
      scanf("%d",&n);
      printf("No.%d value of Fibonacci sequence is %d\n",n,fcc(n));
}