递归

• 何为递归
• • 递归定义
  • 何时使用递归
  • 递归模型
  • 递归算法的执行过程
• 递归算法设计
• • 递归算法设计的一般步骤
  • 递归数据结构及其递归算法设计
  • • 递归数据结构的定义
    • 基于递归数据结构的递归算法设计
    • 基于归纳思想的递归算法设计
  • 递归算法设计示例

何为递归

递归定义

在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。
若调用自身，称之为直接递归。若过程或函数p调用过程或函数q，而q又调用p，称之为间接递归。
任何间接递归都可以等价地转换为直接递归。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。
一般来说，能够用递归解决的问题应该满足以下三个条件：
1）需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
2）递归调用的次数必须是有限的。
3）必须有结束递归的条件来终止递归。

何时使用递归

1）定义是递归的
许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci数列等。
2）数据结构是递归的
有些数据结构是递归的。例如单链表就是一种递归数据结构。
3）问题的求解方法是递归的
有些问题的解法是递归的，典型的有Hanoi问题求解。

递归模型

递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例如：

fun(1)=1                    (1)   
fun(n)=n*fun(n-1)     n>1   (2) 

其中，第一个式子给出了递归的终止条件，第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系，我们把第一个式子称为递归出口，把第二个式子称为递归体。

递归算法的执行过程

• 一个正确的递归程序虽然每次调用的是相同的子程序，但它的参量、输入数据等均有变化。
• 在正常的情况下，随着调用的不断深入，必定会出现调用到某一层的函数时，不再执行递归调用而终止函数的执行，遇到递归出口便是这种情况。
• 递归调用是函数嵌套调用的一种特殊情况，即它是调用自身代码。也可以把每一次递归调用理解成调用自身代码的一个复制件。
• 由于每次调用时，它的参量和局部变量均不相同，因而也就保证了各个复制件执行时的独立性。
• 系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参量值。
• 这些单元以系统栈的形式存放，每调用一次进栈一次，当返回时执行出栈操作，把当前栈顶保留的值送回相应的参量中进行恢复，并按栈顶中的返回地址，从断点继续执行。

归纳起来，递归调用的实现是分两步进行的，第一步是分解过程，即用递归体将“大问题”分解成“小问题”，直到递归出口为止，然后进行第二步的求值过程，即已知“小问题”，计算“大问题”。

递归算法设计

递归算法设计的一般步骤

递归算法设计先要给出递归模型，再转换成对应的C/C++语言函数。
获取递归模型的步骤如下：
1）对原问题f(s_n)进行分析，抽象出合理的“小问题”f(s_n-1)
2）假设f(s_n-1)是可解的，在此基础上确定f(s_n)的解，即给出f(s_n)与f(s_n-1)之间的关系
3）确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口

递归数据结构及其递归算法设计

递归数据结构的定义

采用递归方式定义的数据结构称为递归数据结构。在递归数据结构定义中包含的递归运算称为基本递归运算。

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

1）单链表的递归算法设计
在设计不带头结点的单链表的递归算法时：
设求解以L为首结点指针的整个单链表的某功能为“大问题”。
而求解除首结点外余下结点构成的单链表（由L->next标识，而该运算为递归运算）的相同功能为“小问题”。
由大小问题之间的解关系得到递归体。
再考虑特殊情况，通常是单链表为空或者只有一个结点时，这时很容易求解，从而得到递归出口。
2）二叉树的递归算法设计
二叉树是一种典型的递归数据结构，当一棵二叉树采用二叉链b存储时：
设求解以b为根结点的整个二叉树的某功能为“大问题”。
求解其左、右子树的相同功能为“小问题”。
由大小问题之间的解关系得到递归体。
再考虑特殊情况，通常是二叉树为空或者只有一个结点时，这时很容易求解，从而得到递归出口。

基于归纳思想的递归算法设计

基于归纳思想的递归算法设计通常不像基于递归数据结构的递归算法设计那样直观，需要通过对求解问题的深入分析，提炼出求解过程中的相似性而不是数据结构的相似性，这就增加了算法设计的难度。
但现实世界中的许多问题的求解都隐含这种相似性，并体现计算思维的特性。

递归算法设计示例

例1：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p = l3;
    if(l1==NULL&&l2==NULL){
        l3->next=NULL;
    }
    while(l1!=NULL&&l2!=NULL){
        if(l1->val < l2->val){
            p->next=l1;
            p=l1;
            l1=l1->next;
        }else{
            p->next=l2;
            p=l2;
            l2=l2->next;
        }
    }
    if(l1!=NULL){
        p->next=l1;
    }
    if(l2!=NULL){
        p->next=l2;
    }
    return l3->next;
}

例2：给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回false。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head){
    int l=0;
    int a[100000];
    while(head!=NULL){
        a[l]=head->val;
        l++;
        head=head->next;
    }
    bool huiwen = true;
    for(int i=l/2-1;i>=0;i--){
        if(a[i]!=a[l-i-1]){
            huiwen=false;
        }
    }
    return huiwen;
}

例3：n皇后问题
【问题描述】在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。如下图所示是6皇后问题的一个解。

q[1…6]={2，4，6，1，3，5}
【问题求解】

对于(i，j)位置上的皇后，是否与已放好的皇后(k，q[k])（1≤k≤i-1）有冲突呢？

• 显然它们不同列，若同列则有：q[k]==j；
• 对角线有两条，若它们在任一条对角线上，则构成一个等边直角三角形，即|q[k]-j|==|i-k|。

(q[k]==j) || (abs(q[k]-j)==abs(i-k))

设queen(i，n)是在1～i-1列上已经放好了i-1个皇后，用于在i～n行放置n-i+1个皇后，则queen(i+1，n)表示在1～i行上已经放好了i个皇后，用于在i+1～n行放置n-i个皇后。
queen(i+1，n)比queen(i，n)少放置一个皇后。所以queen(i+1，n)是“小问题”，queen(i，n)是“大问题”。

queen(i，n) ≡ n个皇后放置完毕，输出一个解 若i>n
queen(i，n) ≡ 在第i行的合适的位置（i,j） 其他情况
在其上放置一个皇后;
queen(i+1，n);

bool place(int i,int j)		//测试(i,j)位置能否摆放皇后
{   if (i==1) return true;		//第一个皇后总是可以放置
    int k=1;
    while (k<i)			//k=1～i-1是已放置了皇后的行
    {	if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)))
	    return false;
	k++;
    }
    return true;
}
void queen(int i,int n)		//放置1～i的皇后
{   if (i>n) 
	dispasolution(n);		//所有皇后放置结束
    else
    {	for (int j=1;j<=n;j++)	//在第i行上试探每一个列j
	    if (place(i,j))		//在第i行上找到一个合适位置(i,j)
	    {	q[i]=j;
		queen(i+1,n);
	    }
    }
}