C语言中的递归：原理、实例与练习

C语言中的递归：原理、实例与练习

引用

CSDN

1.

https://m.blog.csdn.net/good_afternoon6/article/details/145952042

递归是编程中一个非常重要的概念，它允许函数调用自身来解决问题。虽然递归的实现相对简洁，但理解其原理和使用场景可能需要一些时间。本文将通过多个实例，帮助读者深入理解递归的概念及其在C语言中的应用。

1. 什么是递归？

递归是一种在函数定义中直接调用自身的编程技术。递归函数的核心在于将大问题分解为小问题，然后通过解决这些小问题来解决大问题。让我们通过一个经典的故事来理解递归的概念：

从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲……

这个故事就是一个递归的例子，故事中的每个层次都在重复相同的内容，直到某个条件终止。

递归函数的核心在于将大问题分解为小问题，然后通过解决这些小问题来解决大问题。接下来我们通过具体例子来解释递归。

2. 举例说明

2.1 求 n 的阶乘

阶乘是一个经典的递归示例。对于一个正整数 n，n 的阶乘可以通过连乘积来定义：n! = 1 * 2 * … * (n-1) * n，而且规定 0 的阶乘为 1。例如：

• 4！=1 * 2 * 3 * 4
• 5！=1 * 2 * 3 * 4 * 5

观察这些阶乘，可以发现：

• 5！= 4！*5
• 6！= 5！*6
• ...

以此类推，可以得到 n！=(n - 1)！n。而 (n - 1)！= (n - 2)！(n - 1)，要得到 (n - 2)！又要往后推，直到碰到 1！=0！*1，因为 0！=1，所以往上返回 1！=1，2！=2，一层层往上回推，最终得到结果。

不知道大家有没有听过一句话 “不撞南墙不回头”，如果把代码运行的流程比作那个人，则那堵南墙就是 0！= 1，只有代码执行碰到了这堵墙才会回头返回值，我们把一直前进的过程叫 “递”，把在撞完南墙后返回的过程叫 “归”。

2.2 斐波那契数列

斐波那契数列的定义是从0和1开始，后续的每一项都是前两项的和，即1、1、2、3、5、8、13、21、34……浅浅分析一下，要写递归时最重要的是要找到限制条件和递归公式，我们可以发现第 1 项，第 2 项都是有固定值的，所以我们的递推应该从第 3 项开始，这便是我们的限制条件；而我们的递推公式也很好找，就是后一项都是前两项的和。

都运行成功！这样看起来是没问题的，但为什么说要通过这个例子来解释地柜的缺点呢？这时我们不妨试一下当n = 40,n = 50时，你会发现，计算机需要一会才能计算出来。这与我们斐波那契数列的递推公式有关，斐波那契数列的递推公式是多分支结构的，这会使很多数据都被重复计算了很多次，例如图中的 fib( 48 )和 fib( 47 )，越到后面的数会重复越来越多次。

由此我们便可以总结出递归的缺点：

1. 可能会占用很多的栈区空间，浪费内存
2. 效率较低，在数据量较大时，会多次重复计算数据

然而递归也不是没有优点，递归的优势在于简洁，递归的代码量对比其他方法较少，且只要根据公式就能写。

3. 执行递归的条件

递归要存在限制条件，递归不是像我们开头举例的那个故事，永远停不下，当满足这个条件时，递归将不再延续，每次递归调用函数之后会越来越接近这个限制条件。如果没有存在这个限制条件，就可能会出现栈溢出。每一次调用函数时都会向内存栈区申请一块空间，如果没有限制条件，就会一直申请空间，可是栈区的空间是有限的，此时就会出现栈溢出。

4. 练习推荐

关于递归的练习，如果大家想进一步了解递归，推荐汉诺塔问题。汉诺塔问题是递归的经典案例。有三根柱子A、B、C，初始时在A柱上按顺序从上到下叠放着n个盘子。目标是将所有盘子移动到C柱上，且移动过程中需满足以下规则：

1. 每次只能移动一个盘子；
2. 大盘子不能放在小盘子上面。

请编写一个递归函数 hanoi，实现将n个盘子从A柱移动到C柱的过程，并打印每一步的移动操作。

下面是代码展示，大家可以先思考先尝试，看一遍代码解析，理解后再自己尝试把代码敲出来。

#include <stdio.h>

// 定义递归函数hanoi，参数分别为盘子数量n、起始柱a、目标柱c、辅助柱b
void hanoi(int n, char a, char c, char b) {
    // 递归终止条件：当n=1时，直接将盘子从a移动到c
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", a, c);
        return;
    }
    // 将n-1个盘子从a移动到b，借助c柱
    hanoi(n - 1, a, b, c);
    // 将第n个盘子从a移动到c
    printf("Move disk %d from %c to %c\n", n, a, c);
    // 将n-1个盘子从b移动到c，借助a柱
    hanoi(n - 1, b, c, a);
}

int main() {
    int n;
    printf("请输入盘子的数量: ");
    scanf("%d", &n);
    printf("汉诺塔移动过程如下:\n");
    hanoi(n, 'A', 'C', 'B'); // 调用递归函数
    return 0;
}

递归算是我最近在学习中遇到的比较难的一个知识点，分享出来，希望大家可以更深刻理解递归。