数据结构——4.递归

递归

直接递归和间接递归（两个函数互相调用）。

如果一个递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。

尾递归算法：可以用循环语句转换成等价的非递归算法

其他递归算法：可以通过栈来转换为等价的非递归算法

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

一般地，一个递归模型是由递归出口（fun(1)=1）和递归体（fun(n)=n*fun(n-1)）两部分组成。

递归算法设计的步骤

- 设计求解问题的递归模型

- 转换成对应的递归算法

求递归模型的步骤：

(1)对原问题f(s)进行分析，称为“大问题”，假设出合理的“小问题”；

(2)假设f(s’)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s’)之间的关系 → 递归体。

(3)确定一个特定情况（如f(1)或f(0)）的解 → 递归出口。

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

递归数据结构的数据特别适合递归处理 → 递归算法。

//正向显示所有节点值
void traverse(Node *L){
    if(L==NULL) return;
    printf("%d",L->data);
    traverse(L->next);
}
//反向显示所有节点值
void traverseR(Node *L){
    if(L==NULL) return;
    traverseR(L->next);
    printf("%d",L->data);
}

基于递归求解方法的递归算法设计：

采用递归方法求解问题时，需要对问题本身进行分析，确定大、小问题解之间的关系，构造合理的递归体。

- 确定问题的形式化描述

- 确定哪些是大问题，哪些是小问题

- 确定大、小问题的关系

- 确定特殊（递归结束）的情况

例题：假设a素组含有1,2,…,n,求其全排列。

解：设f(a,n,k)为a[0..k]（k+1个元素）的所有元素的全排序，为大问题。

则f(a,n,k-1)为a[0..k-1]（k个元素）的所有元素的全排序，为小问题。

void perm(inta[],int n,int k){
    int i,j;
    if(k==0){
        for(j=0;j<n;k++)
            printf("%d",a[j]);
        printf("\n");
    }else
        for(i=0;i<=k;i++){
            swap(a[k],a[i]);
            perm(a,n,k-1);
            swap(a[k],a[i]);
        }
}

递归调用后面的语句表示该子问题执行完毕后要完成的功能。

void fun(int n){
    if(n>=1){
        printf("n1=%d\n",n);
        fun(n-1);
        printf("n2=%d\n",n);
    }
}

数据结构——4.递归

递归

递归算法设计的步骤

Comments