C 递归详解（通俗易懂）

系统管理员 2023-09-25 19:43 67阅读 0赞

**目录**

一、定义

1.概述

2.条件

3.比较

二、 如何理解递归？

1.函数调用其他函数示例 :

2.函数调用函数自身示例 :

3.函数调用自身的底层操作 :

①在主调函数调用被调函数之前——

②在被调函数返回主调函数之前——

③在出现多个函数相互调用的情况时——

三、递归的具体实例

1.求1~100的和 :

思路 :

代码 :

优化 :

2. 汉诺塔问题 :

背景 :

思路 :

代码 :

3.斐波那契数 :

介绍 :

思路 :

代码 :

--------------------

## 一、定义 ##

### 1.概述 ###

> **递归（Recursion）**，又称递回，**是指一个函数直接或间接地实现自调用**。在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环。
> 
> 计算机科学家**尼克劳斯·维尔特**如此描述递归：
> 
> **“** 递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。**”**
> 
> *——尼克劳斯·维尔特*

### 2.条件 ###

> **①递归必须设置一个明确的终止条件，当满足该条件时，递归停止；不满足该条件时，继续递归。**PS : 如果一个递归没有设置终止条件，那么它会无限制地递归下去，形成死递归（类似于死循环），称为“死龟了”。
> 
> **②一个使用了递归的函数，其处理的数据规模一定是在递减的**。即，一个有效的递归，它的递归总次数是一定的，执行的次数越多，剩余的规模就越小。

### 3.比较 ###

> 这里的“比较”，指的是**递归和循环的比较**。
> 
> 理论上讲，**可以用循环解决的问题都可以转化为用递归解决；但是用递归解决的的问题有时候并不能用循环解决**。
> 
> 递归结构简洁，更易理解，但是递归所需存储空间大，运行速度慢；
> 
> 循环结构复杂，不易理解，但是循环所需存储空间小，运行速度快。

--------------------

## 二、 如何理解递归？ ##

### 1.函数调用其他函数示例 : ###

**递归本质上利用的栈的原理，满足“先进后出”的特点**。要想理解递归，必须先理解函数中是如何调用其他函数的，我们先来看下面**一段代码 :**

# include <stdio.h>
    
    void f1();
    void f2();
    void f3();
    
    int main(void)
    {
        f1();
    
        return 0;
    }
    
    void f1()
    {
        f2();
        printf("AAAAA\n");
        return;
    }
    
    void f2()
    {
        f3();
        printf("BBBBB\n");
        return;
    }
    
    void f3()
    {
        printf("CCCCC\n");
        return;
    }

你认为以上代码的输出结果是什么？**输出结果如下 :**

![68f1d4178a4542719e994922e133958c.png][]

**解释 :**   
main函数先进栈，**main函数中调用了f1函数，因此f1函数会进栈；因为f1函数中又调用了f2函数，因此f2函数接着进栈；又因为f2函数中又调用了f3函数，所以f3函数跟着进栈**。  
**根据栈“先进后出”的特点**，f3函数最后进栈，就要最先出栈，而f3中的代码执行完毕后，打印出CCCCC，继而返回f2中；f2函数执行完毕后，打印出BBBBB，接着f2出栈，返回f1中；f1再打印出AAAAA，最后f1出栈；所以**出栈的顺序是f3 ——> f2 ——> f1**。  
那么递归其实就是把“函数中调用其他函数”，给变成了“函数中调用函数自己本身”，同样是栈的原理，同样满足“先进后出”的特点。

### 2.函数调用函数自身示例 : ###

我们再来看一段简单的**递归求某个数阶乘的代码，如下 :**

# include <stdio.h>
    
    int factorial(int);
    
    int main(void)
    {
        int factorial_value = factorial(4);
        printf("4的阶乘 = %d", factorial_value);
    
        return 0;
    }
    
    int factorial(int n)
    {
        if (n == 1 || n == 0)
            return 1;
        return n * factorial(n - 1);
    }

**运行结果 :**

![b3a6ddb1417746468900be39610fc701.png][]

**解释 :**

首先我们可以看到，这段代码的目的就是求4的阶乘。main函数先进栈，main函数中调用了factorial方法（factorial \[fækˈtɔriəl\] 就是“阶乘”的意思），factorial方法要进栈，此时我们传入的实参 = 4；接着，因为4不满足factorial方法中if语句的判断条件，因此要执行return语句，而return语句的内容"n \* factorial(n - 1)"中又调用了factorial函数自身，只不过这次调用的效果是factorial(3)了，所以**factorial(3)方法中包含的局部变量要进栈**；同理，factorial(2)方法包含的局部变量进栈；factorial(2)方法中有调用factorial(1)方法，所以factorial(1)方法包含的局部变量最后进栈。所以**整个求4的阶乘的递归过程中，factorial函数的****压栈顺序为：****factorial(4) ——> factorial(3) ——> factorial(2) ——> factorial(1)**  
在factorial(1)方法中，满足if条件语句，因此**factorial(1)方法要返回1**，接着，factorial(1)方法执行完毕，factorial(1)方法出栈，回到factorial(2)方法；**factorial(2)方法返回 2 \* factorial(1) = 2 \* (1)**，接着factorial(2)方法出栈，回到factorial(3)方法；**factorial(3)方法返回3 \* (2 \* 1)**，接着factorial(3)方法出栈，回到factorial(4)方法；**factorial(4)方法返回4 \* (3 \* 2 \* 1)**。所以**整个求4的阶乘的递归过程中，factorial函数的****出栈顺序为：****factorial(4) ——> factorial(3) ——> factorial(2) ——> factorial(1)**。直到递归到factorial(1)时，停止递归，开始逐层返回。

我们可以对以上代码进行优化，使得我们可以求任意一个数的阶乘，**代码如下 :**

# include <stdio.h>
    
    int factorial(int);
    
    int main(void)
    {
        printf("请输入你想求阶乘的数：（提示 : 大于等于0的整型数据）");
        int i;
        scanf("%d", &i);
        int factorial_value = factorial(i);
        
        if (factorial_value == -1)
            printf("请传入大于等于0的数！");
        else
            printf("\n所求数%d的阶乘= %d\n", i, factorial_value);
    
        return 0;
    }
    
    int factorial(int n)
    {
        if (n < 0)
        {
            return -1;
        }
        else if (n == 0 || n == 1)
            return 1;
        return n * factorial(n - 1);
    }

**运行效果 : (如下GIF图)**

![23196c1a18604a6badd838442d0e8a0e.gif][]

### 3.函数调用自身的底层操作 : ###

#### ①在主调函数调用被调函数之前—— ####

**1°** **系统要将传入的实参和主调函数的地址等信息传递给被调函数保存**。传递"主调函数的地址"，其目的是为了确保程序执行的连续性，即当被调函数执行完毕准备出栈时，可以根据这个地址来找到接下来需要执行的语句。  
**2°** 系统要**为被调函数的局部变量（包括形参和方法体定义的变量）分配内存空间**。  
 **3°** 将**控制权限由主调函数转移到被调函数的入口**，准备执行被调函数。

#### ②在被调函数返回主调函数之前—— ####

**1°** 系统要**保存被调函数的返回结果**，即对它做一个备份，用于返回给主调函数。  
**2°** 系统要**释放掉为被调函数分配的内存空间**。（不包括动态内存）  
**3°** 按照被调函数保存的返回地址，**将控制权限由被调函数转移到主调函数**。

#### ③在出现多个函数相互调用的情况时—— ####

**1°** 按照“**后调用，先返回**”的原则，所涉及到的信息传递和控制转移等操作需要借助“栈”来实现。  
**2°** 系统会将整个程序运行所需的内存空间安排在一个栈中，每**当调用一个函数时，就在栈顶分配一块空间用于压栈；每当退出一个函数时，就释放这块区域，完成出栈操作；当前运行的函数永远位于栈顶的位置**。

--------------------

## 三、递归的具体实例 ##

### 1.求1~100的和 : ###

#### **思路 :**  ####

类似于上文中求阶乘的步骤，我们可以**先进行一个if条件语句的判断——n是否等于1，该判断可作为递归结束的条件**；**当n不满足等于1的条件时，就return n + f(n - 1)，f代表当前求和的函数**。

#### **代码 :**  ####

# include <stdio.h>
    
    int sum(int);
    
    int main(void)
    {
    
        printf("\n1~100的和 = ");
        int sum_value = sum(100);
        printf("%d\n", sum_value);
    
        return 0;
    }
    
    int sum(int n)
    {
        if (n == 1)
            return 1;
        return n + sum(n - 1);
    }

**运行结果 :**

![180971975e0a4adba4f012543bb5a709.png][]

#### **优化 :**  ####

我们可以**令用户自定义传入sum函数的实参，达到求"1~n的和"的目的**。**代码如下 :**

# include <stdio.h>
    
    int sum(int);
    
    int main(void)
    {
        printf("请输入你想求的1到某个数的和：");
        int n;
        scanf("%d", &n);
    
        int sum_value = sum(n);
        if (sum_value != -1)
        {
            printf("\n1~%d的和 = ", n);
            printf("%d\n", sum_value);
        }
        else 
            printf("请输入合法的数字！");
    
        return 0;
    }
    
    int sum(int n)
    {
        if (n < 1)
            return -1;
        else if (n == 1)
            return 1;
        return n + sum(n - 1);
    }

**运行效果：（如下GIF图）**

![e09c0d20cbd6482b8397c0f68eb9460e.gif][]

### 2. 汉诺塔问题 : ###

####  **背景 :**  ####

传说越南河内某间寺院有三根银棒，上串 **64 个**金盘。寺院里的僧侣依照一个古老的预言，以特定规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。**移动金盘的规则如下——**  
**①**每次只能移动一个圆盘；  
**②**大盘不能叠在小盘上面。  
**③**设三根银棒分别为A，B，C；最终要将A棒上的64个金盘移动到C棒上，移动过程中可借助B棒来临时存放金盘。

####  **思路 :**  ####

仍是**递归的思想**——  
**①**我们先从最简单的1个金盘说起，若想将一个金盘从A棒移动到C棒，直接移动就可以，不需要借助B棒。  
**②**当A棒有2个金盘时，我们可以先将上面的第一个金盘放到B棒上；再把A棒的第二个金盘放到C棒；最后将B棒的第一个金盘放到C棒。(该目标的实现借助了B棒，B棒上临时存放了第1个金盘）  
**③**当A棒有3个金盘时，我们可以设法将A棒上面的2个金盘放到B棒上，将第三个金盘从A棒移动到C棒，再设法将B棒临时存放的两个金盘放到C棒上。其中，**“设法将A棒上面的2个金盘放到B棒上” 和 “设法将B棒上面的两个金盘放到C棒上” ，这两个步骤其实就是在重复②的步骤**。  
**④通过③我们可知，金盘的数量每增加1个，其实都是在重复之前金盘数量时的步骤，最核心的步骤就是将A棒最下面的那个最大的金盘从A棒放到C棒**。而要想实现最核心的步骤，**必须分三步走：****1°** **先设法将A棒上面的n-1个金盘借助C棒移动到B棒，使A棒只剩下最下面的最大的金盘，同时C棒为空**；这样才能**2°** **接着把最大的金盘从A移动到C**；之后，再**3°** **设法将B棒上面的n - 1个金盘借助A棒移动到C棒**。

#### **代码 :**  ####

# include <stdio.h>
    
    int count = 0;
    void hanoi(int, char, char, char);
    
    int main(void)
    {
        printf("请输入汉诺塔的层数, floors = ");
        int floors;
        scanf("%d", &floors);
    
        hanoi(floors, 'A','B','C');
        if (count > 0)
            printf("总共需要执行的步骤有%d步\n", count);
    
        return 0;
    }
    
    void hanoi(int n, char a, char b, char c)
    {
        if (n < 1)
        {
            printf("请传入合法有效的数据！");
            return;
        }
        else if (n == 1)
        {
            printf("%c --> %c\n", a,c);
            ++count;
            return;
        }
    
        hanoi(n - 1, a,c,b);
        printf("%c --> %c\n", a,c);
        count++;
        hanoi(n - 1, b,a,c);
    
        return;
    }
    
    /*
        注意 : 
        ①hanoi(n - 1, a,c,b) 和 hanoi(n - 1, b,a,c)，这两个步骤是相互联系的。
        ②else if语句中的printf语句，其目的是为了帮助完成hanoi（n - 1, a,c,b)操作；
         最后的printf语句，其目的是完成最核心步骤————将最大的盘从A棒移动到C棒。
    */

**运行效果 : (如下GIF图）**

![59fa9d1abd404cd9b79439b59e619ad4.gif][]

### 3.斐波那契数 : ###

#### **介绍 :**  ####

**Fibonacci\[/ˌfɪbəˈnɑːtʃi/\]，斐波那契数**（意大利语：Successione di Fibonacci），又译为菲波拿契数、菲波那西数、斐氏数、黄金分割数。**所形成的数列称为斐波那契数列，又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列**。这个数列是由意大利数学家斐波那契在他的《算盘书》中提出。  
**在数学上，斐波那契数是以递归的方法来定义**：  
**令F0 = 0; F1 = 1; 则Fn = F(n - 1) + F(n - 2)，其中n ≥2。即——从数列的第三项开始，每一项的值等于前面两项之和**，称为斐波那契数列。斐波那契数列的前几项如下所示 :

![efe7dc5d6108486880acbc76181bb541.png][]

**PS : 0不是第一项，而是第零项，斐波那契数列在文本上从1开始。**

#### **思路 :**  ####

**设n代表斐波那契数列的第n项，当n等于1或者等于2时，可以直接返回1**；**当n大于2时，要想求出斐波纳契数列的第n项，必须知道它前面的两项分别是多少，而要想知道它前面的两项分别是多少，就又得知道这两项再分别往前的两项是多少**，**依次递归下去，直到n == 1或者n == 2的情况时，return 1；接着再逐层返回，回到你想求出的第n项**。

#### **代码 :**  ####

/*
        斐波那契数列
        2023.4.1
    */
    
    # include <stdio.h>
    
    int fibonacci(int);
    
    int main(void)
    {
        printf("请输入你想输出斐波那契数列的前几项？\nnum = ");
        int num;
        scanf("%d", &num);
    
        if (fibonacci(num) == -1)
        {
            printf("请输入合法数据!");
        }
        else 
        {
            int i;
            for (i = 1; i <= num; ++i)
            {
                printf("%d\t", fibonacci(i));
            }
        }
    
        return 0;
    }
    
    int fibonacci(int n)
    {
        if (n < 1)
            return -1;
        else if (n == 1 || n == 2)
            return 1;
    
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

**运行效果：（如下GIF图所示）**

![4ff2d8f8edaa4542b23f2b4e63f363a0.gif][]

[68f1d4178a4542719e994922e133958c.png]: https://img-blog.csdnimg.cn/68f1d4178a4542719e994922e133958c.png
[b3a6ddb1417746468900be39610fc701.png]: https://img-blog.csdnimg.cn/b3a6ddb1417746468900be39610fc701.png
[23196c1a18604a6badd838442d0e8a0e.gif]: https://img-blog.csdnimg.cn/23196c1a18604a6badd838442d0e8a0e.gif
[180971975e0a4adba4f012543bb5a709.png]: https://img-blog.csdnimg.cn/180971975e0a4adba4f012543bb5a709.png
[e09c0d20cbd6482b8397c0f68eb9460e.gif]: https://img-blog.csdnimg.cn/e09c0d20cbd6482b8397c0f68eb9460e.gif
[59fa9d1abd404cd9b79439b59e619ad4.gif]: https://img-blog.csdnimg.cn/59fa9d1abd404cd9b79439b59e619ad4.gif
[efe7dc5d6108486880acbc76181bb541.png]: https://img-blog.csdnimg.cn/efe7dc5d6108486880acbc76181bb541.png
[4ff2d8f8edaa4542b23f2b4e63f363a0.gif]: https://img-blog.csdnimg.cn/4ff2d8f8edaa4542b23f2b4e63f363a0.gif