探索递归在C语言中的奇妙之旅

1. 引言

本篇博客将介绍递归在C语言中的应用。递归是一种函数调用自身的编程技巧，它能够解决一些需要重复执行相似操作的问题。我们将讨论递归的基本概念、递归展开的理解以及通项公式的递归写法。

2. 递归的基本概念

2.1 递归函数的定义

递归函数是一种调用自身的函数。它通过将问题分解为更小的子问题，并通过调用自身来解决这些子问题。

2.2 递归的终止条件

递归函数必须包含一个终止条件，也称为基本情况。当满足终止条件时，递归函数将不再调用自身，从而避免无限循环。

3. 递归展开的理解

3.1 示例1: 递归展开过程

考虑以下示例代码：

void fun(int i)
{
    if (i < 5)
    {
        fun(i+1);
        printf("%d ", i);
    }
}

int main(void)
{
    fun(1);
    return 0;
}

在这个例子中，fun() 函数通过递归调用自身来输出数字。当 i 小于5时，函数会先递归调用 fun(i+1)，然后再打印当前的 i 值。

递归展开的过程如下：

fun(1)
  fun(2)
    fun(3)
      fun(4)
        fun(5)
      printf("4 ")
    printf("3 ")
  printf("2 ")
printf("1 ")

最终的输出结果为：1 2 3 4。

3.2 示例2: 递归展开的不同输出方式

如果我们将 printf("%d ", i) 语句移动到递归调用之前，代码如下：

void fun(int i)
{
    if (i < 5)
    {
        printf("%d ", i);
        fun(i+1);
    }
}

int main(void)
{
    fun(

1);
    return 0;
}

递归展开的过程如下：

fun(1)
  printf("1 ")
  fun(2)
    printf("2 ")
    fun(3)
      printf("3 ")
      fun(4)
        printf("4 ")
        fun(5)

最终的输出结果为：1 2 3 4。

这个示例展示了递归展开中语句位置的变化对输出结果的影响。

4. 通项公式的递归写法

4.1 示例1: 斐波那契数列

斐波那契数列是一个经典的递归问题，它的通项公式为 f(n) = f(n-1) + f(n-2)，其中 f(1) = 0，f(2) = 1。

以下是斐波那契数列的递归写法：

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

通过调用 fibonacci(n) 函数，我们可以计算斐波那契数列的第 n 项。

4.2 示例2: 阶乘

阶乘是另一个常见的递归问题，它的通项公式为 f(n) = n * f(n-1)，其中 f(1) = 1。

以下是阶乘的递归写法：

int factorial(int n)
{
    if (n == 1)
        return 1;
    else
        return n * factorial(n-1);
}

通过调用 factorial(n) 函数，我们可以计算阶乘的值。

5. 结论

递归是一种强大的编程技巧，能够解决需要重复执行相似操作的问题。在C语言中，我们可以利用递归函数和递归展开来实现复杂的计算和操作。递归的正确使用需要明确终止条件，并注意递归展开的顺序对输出结果的影响。

本篇博客介绍了递归的基本概念、递归展开的理解以及通项公式的递归写法，并提供了示例代码来帮助读者更好地理解和应用递归。

6. 参考资料

C Programming Language - Wikipedia
C++ Primer by Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo
Introduction to Recursive Functions in C

江南侠客（上海）

目录