5.2栈和递归

5.2.1 函数调用栈

大多数CPU上的程序实现使用栈来支持函数调用操作。单个函数调用所使用的结构被称为栈帧结构，每次函数调用的时候都会自动地创建一帧，保存返回地址，函数实参和局部变量值等等，并将该帧压入调用栈，如果在该函数返回之前又有新函数发生调用，那继续压栈，执行完了再出栈。

5.2.2 递归调用的实现

递归是函数调用的一种特殊形式，调用自身代码。其入栈出栈情况如下。
image.png
再举个例子：

例子hh

  1. int S(int n)
  2. {
  3.     return(n<=0)?0 : S(n-1)+n;
  4. }
  5. int main()
  6. {
  7.     printf("%d\n",S(1));
  8.     return 1;
  9. }

程序执行的时候使用一个栈来保存调用过程的信息，这些信息用main()、S(0)和S(1)来表示，那么自栈底到栈顶保存的信息的顺序是怎样的？
首先main()函数开始执行程序，将main()进栈，遇到调用S(1)，将S(1)进栈，在执行递归函数S(1)时又遇到S(0)，再将S(0)进栈。所以自栈底到栈顶保存的信息顺序是main()->S(1)->S(0)。

5.2.3 递归到非递归的转换。

如果一个递归过程或者递归函数中的递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。
尾递归算法一般可以通过循环和迭代方式转换为等价的非递归算法，
比如斐波那契数列：

斐波那契数列的非递归算法

  1. int fib(int n)
  2. {
  3.     int a = 1, b = 1, s, i;
  4.     if(n == 1|| n == 2)
  5.     {
  6.         return (1);
  7.     }
  8.     else
  9.     {
  10.         for(i = 3;i<=n;i++)
  11.         {
  12.             s = a+b;
  13.             a = b;
  14.             b = s;
  15.         }
  16.     return s;
  17.     }
  18. }

5.3 递归算法的设计

5.3.1 递归算法设计的步骤

分而治之，讲一个大问题分解成若干的子问题，子问题的求解是独立的，求解过程对应一个递归树。

求接问题递归模型的步骤如下

  1. 队员问题f(n)进行分析，提出合理的子问题f(n-1)
  2. 假设子问题f(n-1)是可解的，在此基础上确定大问题f(n)的解，也就是给出f(n)和f(n-1)之间的关系，确定递归体。
  3. 确定一个特定情况如f(1)或者f(2)的解，由此作为递归出口。

5.3.2 基于递归数据结构的递归算法设计

具有递归特性的数据结构被称为递归数据结构。通常采用递归方式定义。
我们定义一个递归数据结构为:
RD=(D,Op) D = {di}(1<=i<=n)为构成该数据结构的元素集合，Op是递归运算的集合，Op=(opj)(1<=j<=m)。对于上述递归元素若全是正整数，那么D为正整数的集合，Op（op1，op2）由两个基本递归运算符构成，op1定义为op1（n）= n-1；op2的定义为op2（n）=n+1（n>=1）。
对于不带头结点的单链表，其节点类型为LinkNode,每个节点的next为LinkNode类型的指针，这样的单链表通过首结点指针来标识，定义如下：
SL = (D,Op)
D是部分或全部节点构成的单链表集合，那Op就是节点指向的语句 op1 (L) = L->next。
递归算法设计的第二步是确定递归模型中的递归体。