c语言中什么是递归 经典递归函数例子分享

什么是递归

递归是指函数调用自身的过程。一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，被称为递归函数。

#include <stdio.h>

void recursion(int num)
{
    if (num > 0)
    {
        printf("%d\n", num);
        recursion(num - 1);
    }
}

int main()
{
    int num = 5;
    recursion(num);
    return 0;
}

上面的代码是一个经典的递归代码示例，通过函数recursion自己调用自己的方式，实现输出数字的倒序。

递归的应用

递归可以简洁明了地进行诸如回溯，穷举搜索等一些算法的实现。经典的汉诺塔问题就可以用递归方式进行解答。

#include <stdio.h>

void move(int n, char a, char b, char c)
{
    if (n == 1)
    {
        printf("%c -> %c\n", a, c);
    }
    else
    {
        move(n - 1, a, c, b);
        printf("%c -> %c\n", a, c);
        move(n - 1, b, a, c);
    }
}

int main()
{
    int n = 3;
    move(n, 'A', 'B', 'C');
    return 0;
}

上面的代码是经典的汉诺塔问题，通过递归的方式，实现把n个盘子从A柱移动到C柱的操作。

递归的缺点

虽然递归可以让程序实现简单明了，但是在运行的时候，递归会在函数调用和返回时，消耗大量的内存空间。这会导致程序的运行速度变慢。

#include <stdio.h>

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

int main()
{
    int n = 5;
    int result = fibonacci(n);
    printf("The %dth fibonacci is %d", n, result);
    return 0;
}

上面的代码是斐波那契数列的递归实现，虽然代码简短易懂，但是当n值较大时，递归的运行效率会变得非常慢。

递归的优化

递归的缺陷在于，在每次递归调用的时候，都需要在内存中保留现场。对于求解递归问题需要的空间复杂度的总和，我们称它为递归栈的空间复杂度。采用尾递归或者转换成非递归的方式，可以节省程序运行时的空间。

#include <stdio.h>

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

int main()
{
    int n = 5;
    int result = fibonacci(n, 0, 1);
    printf("The %dth fibonacci is %d", n, result);
    return 0;
}

上面的代码是斐波那契数列的尾递归实现，把递归调用变成了函数参数迭代的方式，大大提高了程序执行效率。