三个例子掌握函数递归

三个例子掌握函数递归

引用

CSDN

1.

https://blog.csdn.net/2401_89044302/article/details/145739330

递归是编程中一种重要的算法思想，它通过将问题分解为更小的子问题来解决问题。本文通过三个具体的代码实例，帮助读者掌握函数递归的概念、实现方式以及适用场景。

递归 —> 大事化小

1.递归思想

递归是将问题转化为相似的较小问题，递推即递推回归。在C语言函数中可体现为函数调用函数自己。

2.函数的递归调用形式

if(递归终止条件成立） //在逐渐调用中接近终止条件
    return 递归公式初值;
else
    return 递归函数调用对应结果值;

3.简单函数递归实例

a.顺序打印数字的每一位
输入 6543
输出 6 5 4 3

void Print(int n)
{
    if (n / 10 != 0)//递归结束条件
        Print(n/10);
    printf("%d ", n % 10);
}

这个函数通过递归调用自身，每次去掉数字的最后一位，直到数字只剩一位为止。然后在回溯的过程中，依次打印每一位数字。

b.计算阶乘
输入 5
输出 120

int Fit(int n)
{
    if (n == 1)//递归结束条件
        return 1;
    else
        return n * Fit(n - 1);
}

这个函数通过递归调用自身，每次将问题规模减小1，直到n等于1时返回1。然后在回溯的过程中，依次计算阶乘的值。

4.递归的适用情况

每次递归调用时占用内存空间，当递归层数过多时浪费栈帧过多且效率过低，也可能造成栈溢出。

例如计算第n个斐波那契数时：

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

递归层数过多会造成栈溢出。解决使用递归调用层数少的问题时是使用递归的合适情形。反之可以选择运行成本较低效率较高的 迭代（通常是循环)。

在上例的体现为：

int Fib(int n)
{
    int a=1, b=1, c=1, i;
    for (i =3; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

这个迭代版本的斐波那契数列计算方法，通过循环和变量交换的方式，避免了递归带来的栈溢出风险，同时提高了计算效率。