递归

一个函数直接或者间接调用自己。

递归要满足三个条件

1. 递归必须有一个明确的终止条件。
2. 该函数所处理的规模必须在递减。
3. 这个转化必须是可解的。

函数的调用

当一个函数的运行期间调用另一个函数时,在运行被调函数之前,系统需要完成三件事:

1. 将所有的实际参数，返回地址（主调函数的下个语句的地址）等信息传递给被调函数保存。
2. 为被调函数的局部变量（也包括形参）分配存储空间。
3. 将控制转移到被调函数的入口。

从被调函数返回主调函数之前，系统也要完成三件事：

1. 保存被调函数的返回结果。
2. 释放被调函数所占的存储空间。
3. 依照被调函数保存的返回地址将控制转移到调用函数。

当有多个函数互相调用时，按照“后调用先返回” 的原则，上述函数之间信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需要的数据空间安排在一个栈中，每当调用一个函数时，就释放它的存储区，就运行出栈操作，当前运行的函数永远都在栈顶的位置。

不同函数之间的调用

#include <stdio.h>

void f();
void g();
void k();

int main(void)
{
    f();

    return 0;
}

void f()
{
    printf("fff\n");
    g();
    printf("111\n")
}

void g()
{
    printf("ggg\n");
    g();
    printf("222\n")
}

void k()
{
    printf("kkk\n");
}

函数自己调用自己

#include <stdio.h>

void f();

int main(void)
{
    f();

    return 0;
}

void f()
{
    printf("fff\n");
    f();
}

当然这么写会溢栈，需要加上条件判断停止函数的调用。

举例

1、求阶乘

使用 for 循环实现:

#include <stdio.h>

int main(void)
{
    int val;
    int i, mut = 1;

    printf("请输入一个数字: ");
    printf("val = ");
    scanf("%d", &val);

    for (i = 1; i < val; ++i)
        mut = mut * i;

    return 0;
}

使用递归实现:

#include <stdio.h>

//假定 n 值是 1 或者大于 1 的值
long f(long n)
{
    if (1 == n)
        return 1;
    else
        return f(n - 1) * n;
}

int main(void)
{
    printf("%ld \n", f(3)); //输出 6
    return 0;
}

2、求 1+2+3+...+100 的和

递归实现:

#include <stdio.h>

long sum(int n)
{
    if (1 == n)
        return 1;
    else
        return n + sum(n - 1);
}

int main(void)
{
    printf("%ld \n", sum(100));
    return 0;
}

循环和递归比较

能用循环实现的，都可以用递归实现。但可用递归实现的，用循环有的很难实现，例如遍历树。

递归：
易于理解（例如用递归遍历树，容易理解，用循环很难实现），但是速度慢，存储空间大。
循环：
不易理解，但是速度快，存储空间小。

递归的应用

• 树和森林就是以递归的方式定义的。
• 树和图的很多算法都是以递归来实现的。
• 很多数学公式就是以递归的方式定义的。