一篇文章带你了解C语言函数递归

什么是函数递归？

函数递归指的是在函数内部调用自身的过程。使用函数递归可以简化程序的逻辑和实现，递归函数可以使代码更加简洁和易读。

如何编写递归函数？

编写递归函数要注意以下几点：

1. 设计好递归终止条件，否则函数将一直递归下去直到栈溢出。
2. 确保每次递归调用后，问题的规模都会减小。
3. 考虑好递归过程中参数的传递方式。

比如，下面我们来看一下一个简单的计算阶乘的递归函数例子：

int factorial(int n)
{
    if(n == 0)
        return 1;

    return n * factorial(n-1);
}

在这个例子中，我们设置了递归终止条件为n等于0，如果n等于0，直接返回1。否则，我们将n乘以factorial(n-1)，实现了递归调用，可以计算出给定n的阶乘。

递归函数的示例

例子1：计算斐波那契数列

斐波那契数列是指从0和1开始，之后的斐波那契数列系数就是由之前的两数相加而得出的。也就是说，第n项的值等于第n-1项和第n-2项的和（n>=3，n∈N*）。

我们可以使用递归函数来计算斐波那契数列，代码如下：

int fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;

    return fibonacci(n-1) + fibonacci(n-2);
}

在这个例子中，我们设置了递归终止条件为n等于1或2时返回1。否则，我们将fibonacci(n-1)和fibonacci(n-2)相加，实现了递归调用，可以计算出斐波那契数列的第n项。

例子2：汉诺塔问题

汉诺塔问题是著名的数学问题，其大致描述如下：有三根柱子A、B、C。A柱子上有n个盘子，盘子大小不等，大的在下面，小的在上面。要求将A柱子上的盘子全部移动到C柱子上，移动过程中可以借助B柱子，但要求每次只能移动一个盘子，且大盘子不能放在小盘子上面。求解移动所有盘子的最短路径。

我们可以使用递归函数来解决汉诺塔问题，代码如下：

void hanoi(int n, char A, char B, char C) 
{
    if (n == 1) 
    {
        printf("Move disk %d from %c to %c\n", n, A, C);
        return; 
    } 

    hanoi(n-1, A, C, B); 
    printf("Move disk %d from %c to %c\n", n, A, C); 
    hanoi(n-1, B, A, C); 
}

在这个例子中，我们将所有盘子分为两部分，一部分为最下面的盘子（即第n个盘子），另一部分为上面的盘子。

我们假设我们已经将上面的盘子移到了B柱子上，现在我们需要将第n个盘子移到C柱子上。因此，我们需要借助B柱子，将上面的盘子从B柱子移到C柱子上。这个过程可以用递归函数来实现，即hanoi(n-1, A, C, B);。递归终止条件为只有一个盘子时，直接将盘子从A柱子移动到C柱子上，即printf("Move disk %d from %c to %c\n", n, A, C);。

当我们将第n个盘子移到C柱子上后，我们需要将上面的盘子从B柱子移到C柱子上。这个过程同样可以用递归函数来实现，即hanoi(n-1, B, A, C);。

通过递归函数的调用，我们可以把所有盘子都从A柱子移到C柱子上，完成最短路径的移动过程。

总结

递归函数可以简化程序实现和逻辑思考，但要注意设置好递归终止条件和参数传递方式。本文介绍了如何编写递归函数，并且通过两个例子的讲解，详细说明了递归函数的使用方法。在实际开发中，递归函数可以广泛应用于各种问题的求解中。