递归

一, 定义

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

    递归必须满足的两个个条件:
    (1) 递归必须得有一个明确的终止条件
    (2) 该函数所处理的数据规模必须在递减, 即总体上 被调用次数不能增加

二, 函数调用

1, 调用其他函数

    如图

2, 调用自己

    必须知道什么时候不调自己
    即, 当满足某个条件时, 返回
    如图

三, 递归举例

1, 求阶乘

    (1) 循环实现

    (2) 递归实现

#include <stdio.h>

// 递归 实现 阶乘
long getTactorial_2(int num)
{
    if (1 == num)
    {
        return 1;
    }
    return num * getTactorial_2( num - 1 );
}

// 循环 实现 阶乘
long getTactorial_1(int num)
{
    int mult = 1;
    for (; num > 0; --num)
    {
        mult *= num;
    }
    return mult;
}

int main(void)
{
    int num;
    printf("输入一个整数: ");
    scanf("%d", &num);
    
    printf("%d 的阶乘是: %ld\n", num, getTactorial_1(num));
    printf("%d 的阶乘是: %ld\n", num, getTactorial_2(num));
    
    return 0;
}

2, 求 1 + 2 + 3 + ... + 99 + 100 的和

#include <stdio.h>

int getSum(int num)
{
    if (1 == num)
    {
        return 1;
    }
    return num + getSum(num - 1);
}

int main(void)
{
    int maxNum;
    printf("输入一个整数: ");
    scanf("%d", &maxNum);

    printf("1 ~ %d 的和 = %d\n", maxNum, getSum(maxNum) );

    return 0;
}

四, 循环 和 递归 优缺点

1, 递归
    (1) 优点
            易于理解(针对数据结构中的 树, 图)
    (2) 缺点
            速度慢(参看引用的函数调用过程)
            存储空间大
2, 循环
    (1) 优点
            速度快
            存储空间小
    (2) 缺点
            不易理解

五, 递归的应用

    树和森林是以递归的方式定义的
    树和图的很多算法都是以递归来是实现的
    很多数学公式都是以递归的方式定义的
        如, 斐波拉契序列 1, 2, 3, 5, 8, 13, ...