c递归算法模型

使用递归算法模型可以较为自然地解决许多问题，尤其是对于那些数据结构层次比较清晰的问题，递归算法模型往往能够提供一种简单清晰的解法。

递归算法模型的核心思想是将一个大问题通过递归的方式拆分为若干个较小的问题，并不断递归下去直到问题变得足够简单，直接求解即可。这个思想实质上也是分治思想的一种应用，将大问题分解为若干个子问题，进而得到子问题的解，最后将子问题的解整合起来得到原问题的解。

但是在使用递归算法模型时也需要注意一些细节问题。以下是一些需要注意的事项：

1. 定义好递归函数的边界条件，避免递归进入无限循环，导致程序崩溃或者降低程序执行效率。

2. 在递归函数中尽可能不要使用全局变量，要使用参数传递的方法来传递函数所需的数据。

3. 递归算法模型的实现过程中如果存在大量计算，则很容易产生栈溢出，因此在使用递归算法模型时需要尽量避免出现超长递归链的情况。

4. 在递归过程中如果需要开辟新的内存空间，则需要注意内存泄漏问题，及时释放不需要的内存空间，避免程序长时间执行后内存溢出。

5. 在递归过程中如果需要访问外部数据结构，一定要注意访问的合法性，避免出现访问越界等错误。

6. 在递归过程中尽量避免使用递归调用层数过多的方式，可以通过设计合理的算法减少递归层数，提高效率。

7. 对于非线性的数据结构（如树、图等），递归算法模型非常适合，但是需要注意一些特殊情况，如避免形成环路等。

总之，递归算法模型能够很好地解决许多问题，但是需要注意细节问题，避免程序出现异常情况，从而实现高效稳定的程序执行。

// n个数阶乘
#include <stdio.h>

int fun(int n)
{
    // 递归终止条件
    if (n <= 1)
    {
        return 1;
    } else {
        return n * fun(n - 1);
    }
    
}

int main()
{
    int sum = fun(5);
    printf("n! = %d\n", sum);

    return 0;
}

// 递归问题——汉诺塔
#include<stdio.h>
int count = 0;
// 在汉诺塔问题中，每次只能移动一个圆盘
// 初始状态下最上边的圆盘编号是1，最底层的圆盘编号是n
// 每次递归调用时，需要将目标柱子和借助柱子的顺序调换，以便于完成移动
// 将n个圆盘从a借助b移到c
void hanoi(int n, char a, char b, char c)
{
    // 递归终止条件
	if (n == 1)
        // 移动操作
		printf("00 第 %-3d 次: %c --> %c\n", ++count, a, c);
	else
	{
        // 移动n-1个圆盘时，需要将这些圆盘从柱子a移动到柱子b，此时柱子c可以作为借助的柱子
        // 因此，需要将顺序调整为acb
		hanoi(n - 1, a, c, b);
        // 当移动晚n-1圆盘后，需要将最后一个圆盘从柱子a移动到柱子c
        // 因此需要输出一条指令，将圆盘a移动到圆盘c
        // 移动操作
		printf("01 第 %-3d 次: %c --> %c\n", ++count, a, c);
        // 然后，需要将n-1个圆盘从柱子b移动到柱子c，此时，柱子a可以作为借助的柱子
        // 因此，需要将顺序调整为bac
		hanoi(n - 1, b, a, c);
	}
}
 
int main()
{
	int n = 0;
	printf("请输入汉诺塔层数：");
	scanf("%d", &n);
	hanoi(n, 'a', 'b', 'c');
	printf("共移动了%d次\n", count);
	return 0;
}

// 斐波拉契数列是由一系列数字组成的序列。
// 该序列中的每一项都是前两项的和，起始项为0和1，第三项为1。
// 斐波拉契数列的前几个数字为：0，1，1，2，3，5，8，13，21，34，55，89，144，...
// 理解斐波拉契数列的方法有许多，其中一个常见的方法是通过兔子繁殖问题。
// 假设有一对新生的兔子，从第三个月开始，每对兔子每月可以繁殖一次，每次繁殖一对兔子。
// 第一个月新生的兔子还太小，不会繁殖，第二个月开始才开始繁殖。
// 设第 $n$ 个月时有 $F(n)$ 对兔子，则 $F(1)=F(2)=1$，当 $n>2$ 时，$F(n)=F(n-1)+F(n-2)$。

// 在代码中我们用递归方式来求解斐波拉契数列。
// 函数的输入为要求的斐波拉契数列的前 $n$ 项，返回值为第 $n$ 项的数值。由于斐波拉契数列的定义中已经规定了前两项为 1 和 1，递归函数中的边界条件
// 即为当 $n<=1$ 时，返回 $n$。在递归调用的过程中，将求解 $n-1$ 项和 $n-2$项的函数值相加即可得到第 $n$ 项的数值。
// 我们在main函数中，通过循环依次输出前 $n$ 项的斐波拉契数列的值。比如当 $n=10$ 时，输出为：0，1，1，2，3，5，8，13，21，34。
// 需要注意的是，递归方式虽然简单，但是其时间复杂度较大，会出现较多重复计算的情况，因此计算高阶项时会比较慢。为了提高效率，可以使用非递归的方式实现斐波拉契数列的求解。

#include <stdio.h>

int fibonacci(int n)
{
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

int main()
{
    int n = 10;
    for (int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");

    return 0;
}

// 迷宫问题
#include <stdio.h>

#define ROW 5
#define COL 5

int maze[ROW][COL] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
};

// 标记是否已经访问过
int visited[ROW][COL] = {0};

int findPath(int i, int j)
{
    // 判断是否越界，如果是则返回0，表示该路径不可行
    if (i < 0 || i >= ROW || j >= COL)
    {
        return 0;
    }
    // 判断是否是障碍物或者已经访问过
    if (maze[i][j] == 1 || visited[i][j] == 1)
    {
        return 0;
    }
    
    // 到达终点返回1，表示找到了一条可行路径
    if (i == ROW - 1 && j == COL - 1)
    {
        visited[i][j] = 1;
        return 1;
    }
    // 如果当前位置不是终点，就标记为已经访问，然后递归调用findPath，分别向上下左右4个方向寻找路径
    visited[i][j] = 1;
    if (findPath(i+1, j) || findPath(i-1, j) || findPath(i, j-1) || findPath(i, j+1))
    {
        return 1;
    }
    // 如果4个方向都没有找到可行路径，就将当前位置标记为为访问，返回0
    visited[i][j] = 0;
    return 0;
}

int main()
{
    // 调用

    if (findPath(0, 0)) {
        printf("找到路径！\n");
    } else {
        printf("没有找到路径。\n");
    }

    return 0;
}