3-递归调用

谁借莪１个温暖的怀抱￠ 2023-08-17 16:02 68阅读 0赞

**1、函数的调用**:当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：

*  将所有的实际参数，返回地址等信息传递给被调函数。
 *  为被调函数的局部变量（也包括形参）分配存储空间
 *  将控制转移到被调函数的入口

#### 自己调用自己
    # include <stdio.h>
    
    void f(int n)
    {
        if (n == 1)
            printf("込込\n");
        else
            f(n-1);
    }
    
    int main(void)
    {
        f(3);
    
        return 0;
    }

2、从被调函数返回主调函数之前，系统也要完成三件事：

*  保存被调函数的返回结果
 *  释放被调函数所占的存储空间
 *  依照被调函数保存的返回地址将控制转移到调用函数

#### 不同函数之间的相互调用
    # include <stdio.h>
    
    void f();
    void g();
    void k();
    
    void f()
    {
        printf("FFFF\n");
        g();
        printf("1111\n");
    }
    
    void g()
    {
        printf("GGGG\n");
        k();
        printf("2222\n");
    }
    
    void k()
    {
        printf("KKKK\n");
    }
    
    int main(void)
    {
        f();
    
        return 0;
    }

3、当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间信息传递和控制转移必须借助“栈”来实现，即系统将整个程序 运行时所需的数据空间安排在一个栈中，每当调用一个函数时，将在栈顶分配一个存储区，进行压栈操作，每当一个函数退出时，就释放它的存储区，就进行出栈操作，当前运行的函数永远都在栈顶位置。

4、A函数调用A函数和A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式比较怪异而已。

#### 2-1： 递归必须满足的三个条件 ####

a、递归必须得有一个明确的终止条件

b、该函数所处理的数据规模必须在递减

c、这个转化必须是可解的

#### 3-1 ：递归和循环的优缺点比较 ####

**递归：**  
1、易于理解

2、速度慢

3、存储空间大

**循环**  
1、不易理解  
2、速度快  
3、存储空间小

#### 4-1 阶乘的循环使用 ####

# include <stdio.h>
    
    int main(void)
    {
        int val;
        int i, mult=1;
    
        printf("请输入一个数字: ");
        printf("val = ");
        scanf("%d", &val);
    
        for (i=1; i<=val; ++i)
            mult = mult * i;
        
        printf("%d的阶乘是：%d\n", val, mult);
    
    
        return 0;
    }

#### 递归求和 ####

# include <stdio.h>
    
    long sum(int n)
    {
        if (1 == n)
            return 1;
        else
            return n + sum(n-1);
    }
    
    int main(void)
    {
        printf("%ld\n", sum(100));
    
        return 0;
    }

#### 4-2 汉诺塔 ####

# include <stdio.h>
    
    void hannuota(int n, char A, char B, char C)
    {
    /*
        如果是1个盘子
            直接将A柱子上的盘子从A移到C
        否则
            先将A柱子上的n-1个盘子借助C移到B
            直接将A柱子上的盘子从A移到C
            最后将B柱子上的n-1个盘子借助A移到C
    */
        if (1 == n)
        {
            printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
        }
        else
        {
            hannuota(n-1, A, C, B);
            printf("将编号为%d的盘子直接从%c柱子移到%c柱子\n", n, A, C);
            hannuota(n-1, B, A, C);
        }
    }
    
    int main(void)
    {
        char ch1 = 'A';
        char ch2 = 'B';
        char ch3 = 'C';
        int n;
    
        printf("请输入要移动盘子的个数: ");
        scanf("%d", &n);
    
        hannuota(n, 'A', 'B', 'C');
    
    
        return 0;
    }

#### 4-3 间接调用自己 ####

# include <stdio.h>
    
    void f(int n)
    {
        g(n);
    }
    
    void g(int m)
    {
        f(m);
    }
    
    int main(void)
    {
    
        return 0;
    }

#### 4-4 A函数调用B函数举例 ####

# include <stdio.h>
    
    int f(int n)
    {
        int i, j;
        n += 2;  // n = n + 2;
        
        return n;
    }
    
    int main(void)
    {
        int val;
    
        val = f(5);
        printf("val = %d\n", val);
    
        return 0;
    }

#### 4-4 A函数调用B函数举例2 ####

# include <stdio.h>
    
    int g(int);
    
    int f(int n)
    {
        if (n < 3)
            printf("込込\n");
        else
            n = f(n-1);
    
        return n;
    }
    
    int g(int m)
    {
        m = m*2;
        return m;
    }
    
    int main(void)
    {
        int val;
    
        val = f(5);
    
        return 0;
    }

#### 4-6 递归递增,处理值的规模在减少 ####

# include <stdio.h>
    
    int g(int);
    
    int f(int n)
    {
        if (n > 7)
            printf("込込\n");
        else
            n = f(n+1);
    
        return n;
    }
    
    int g(int m)
    {
        m = m*2;
        return m;
    }
    
    int main(void)
    {
        int val;
    
        val = f(5);
    
        return 0;
    }

#### 4-7 阶乘的递归实现 ####

# include <stdio.h>
    
    //假定n的值是1或大于1的值
    long f(long n)
    {
        if (1 == n)
            return 1;
        else
            return f(n-1) * n;
    
    }
    
    int main(void)
    {
        printf("%ld\n", f(100));
    
        return 0;
    }

转载于:https://www.cnblogs.com/Guard9/p/11144974.html