递归

落日映苍穹つ 2022-01-13 18:21 195阅读 0赞

1、递归

函数的递归调用；

fun1()-->fun2()-->fun3()-->fun1() 间接递归

fun1()<-->fun1() 直接递归

2、递归调用的性质特点

(1)、函数的调用存在系统资源的消耗,空间及时间的消耗；

(2)、函数的递归调用往往都比较深,因此会产生大量的系统资源的消耗；

(3)、函数的递归调用，若不注意调用的规模(即深度),很容易造成系统资源不足时崩溃的结果；

(4)、递归调用比较符合数学递归定义，因此递归程序都比较好被证明相关算法的正确性及完备性；

(5)、可以先通过递归算法验证程序，在转换成非递归算法以保证效率和安全；

3、递归调用的模型图

**每次都得进行形参压栈，保存现场信息，此时变量名称相同，但是已经是在不同的函数中，具有不同的生命周期；**

模型图：

[![wKioL1gxEpqB8AHEAAAcY\_tePyY524.png-wh\_50][wKioL1gxEpqB8AHEAAAcY_tePyY524.png-wh_50]][wKioL1gxEpqB8AHEAAAcY_tePyY524.png-wh_50]

4、递归程序的设计思路

**(1)、首先要写出递归的结束条件；**

**(2)、其次先只想当前的递归程序该怎么操作(不要去想上一次/下一次的递归)，并写出有效代码；**

**(3)、然后在着重考虑与下一次在调用上的递进关系，此时通过参数加以实现；**

5、递归程序示例

(1)、汉诺塔问题

4层汉诺塔的搬移问题：

代码如下：

#include<stdio.h>
    
    void Hanoii(int n, char s, char a, char t);
    
    void Hanoii(int n, char s, char a, char t)
    {
        if(n > 0)
        {
            Hanoii(n-1, s, t, a);
            printf("%d : %c -> %c\n", n, s, t);
            Hanoii(n-1, a, s, t);
        }
    }
    
    void main(void)
    {
        Hanoii(4, 'A', 'B', 'C');
    }

运行结果：

**[![wKiom1gxFnqRuSGlAABFb52Iu7I133.png-wh\_50][wKiom1gxFnqRuSGlAABFb52Iu7I133.png-wh_50]][wKiom1gxFnqRuSGlAABFb52Iu7I133.png-wh_50]**

(2)、字符串转置

解法一：非递归

代码如下：

#include<stdio.h>
    #include<string.h>
    
    void strrev(char *str);
    void strrev(char *str){
        char *p; 
        char *q; 
        int length = strlen(str);
        int tmp;
    
        p = str;
        q = str+length-1;
    
        while(p < q){ 
            tmp = *p; 
            *p = *q; 
            *q = tmp;
            p++;
            q--;
        }   
    }
    
    int main(void){
        char str[] = "abcdefg";
    
        printf("逆序前:%s\n", str);
        strrev(str);
        printf("逆序后:%s\n", str);
    }

运行结果：

[![wKiom1gxF8-BkljHAAAuJAio36k650.png-wh\_50][wKiom1gxF8-BkljHAAAuJAio36k650.png-wh_50]][wKiom1gxF8-BkljHAAAuJAio36k650.png-wh_50]

解法二：递归

代码如下：

#include<stdio.h>
    #include<string.h>
    
    void strrev_1(char *str, int length);
    void strrev_1(char *str, int length){
        char tmp; 
    
        if(length > 1){ 
            tmp = *str;
            *str = *(str+length-1);
            *(str+length-1) = tmp;
            strrev_1(str+1, length-2);
        }   
        
        }   
    
    
    int main(void){
        char str[] = "abcdefg"; 
        int length = strlen(str);
    
        printf("逆序前:%s\n", str);
        strrev_1(str, length);
        printf("逆序后:%s\n", str);
    
    
        return 0;
    }

运行结果：

[![wKioL1gxGHqCoNRvAAAwcYR8j2U974.png-wh\_50][wKioL1gxGHqCoNRvAAAwcYR8j2U974.png-wh_50]][wKioL1gxGHqCoNRvAAAwcYR8j2U974.png-wh_50]

解法三：递归

代码如下：

#include<stdio.h>
    #include<string.h>
    
    void revStr(char *str, char *tmp);
    void revStr(char *str, char *tmp){
        if(str == NULL || tmp == NULL){
            printf("有为空的,逆序不能进行\n");
            return;
        }   
        if(*str == 0){ 
            return;
        }   
        revStr(str+1, tmp); //用栈实现字符串的逆序,先进后出;
    
        strncat(tmp, str, 1); 
    }
    
    int main(void){
        char str1[80] = "abcdefghijkl";
        char tmp[80];
    
        printf("逆序前:%s\n", str1);
        revStr(str1, tmp);
        printf("逆序后:%s\n", tmp);
    }

运行结果：

[![wKiom1gxGbTyEIj\_AAAyHSm759U759.png-wh\_50][wKiom1gxGbTyEIj_AAAyHSm759U759.png-wh_50]][wKiom1gxGbTyEIj_AAAyHSm759U759.png-wh_50]

转载于:https://blog.51cto.com/wait0804/1874723

[wKioL1gxEpqB8AHEAAAcY_tePyY524.png-wh_50]: /images/20220113/54a6ac53d1af4a12858661e8473d5c0a.png
[wKiom1gxFnqRuSGlAABFb52Iu7I133.png-wh_50]: https://s1.51cto.com/wyfs02/M00/8A/76/wKiom1gxFnqRuSGlAABFb52Iu7I133.png-wh_500x0-wm_3-wmp_4-s_644599905.png
[wKiom1gxF8-BkljHAAAuJAio36k650.png-wh_50]: https://s1.51cto.com/wyfs02/M01/8A/76/wKiom1gxF8-BkljHAAAuJAio36k650.png-wh_500x0-wm_3-wmp_4-s_1480229270.png
[wKioL1gxGHqCoNRvAAAwcYR8j2U974.png-wh_50]: /images/20220113/b89bedc3c174415391daa1b2fdf85a81.png
[wKiom1gxGbTyEIj_AAAyHSm759U759.png-wh_50]: https://s1.51cto.com/wyfs02/M02/8A/76/wKiom1gxGbTyEIj_AAAyHSm759U759.png-wh_500x0-wm_3-wmp_4-s_828611019.png