一. 递归

C/C++ 允许函数调用它自己，这种调用过程称为递归

1.1 什么时候使用递归

一个问题可以分解成具有相同解决思路的子问题、子子问题… 即这些问题都能调用同一个函数

经过层层分解的子问题最后一定是有一个不能再分解的固定值，即终止条件。如果没有的话，就无穷无尽地分解子问题了，这样的问题显然是无解的。

  1. 数据的定义是按递归定义的，如斐波那契数列
  2. 数据结构是按递归定义的，如树
  3. 问题的解法按递归算法实现，如回溯

1.2 递归三要素

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑

1.3 实战演练

  1. 输入一个正整数 N，输出 N! 的值。
#include <stdio.h>

int solveFactorial(int N){
    if(N == 1 || N == 0)
        return 1;
    return N * solveFactorial(N - 1);
}

int main(void){
    printf("Res: %d\n", solveFactorial(3));
    return 0;
}
  1. 求斐波那契数列的第 N 项
#include <stdio.h>

int solveFibonacci(int N){
    if(N == 1 || N == 2)
        return 1;
    return solveFibonacci(N - 1) + solveFibonacci(N - 2);
}

int main(void){
    printf("Res: %d\n", solveFibonacci(4));
    return 0;
}
  1. 一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶。例如：跳上第 1 级台阶只有一种跳法，直接跳一级即可。跳上第 2 级台阶有两种跳法，每次跳 1 级，跳两次；或者一次跳 2 级。问要跳上第 n 级台阶有多少种跳法？
#include <stdio.h>

int solveJumpSteps(int N){
    if(N == 1)
        return 1;
    if(N == 2)
        return 2;
    return solveJumpSteps(N - 1) + solveJumpSteps(N - 2);
}

int main(void){
    printf("Res: %d\n", solveJumpSteps(3));
    return 0;
}

1.4 递归的时间复杂度

递归的时间复杂度为递归的次数 * 每次递归中的操作次数

求 x 的 N 次方

函数 1

int solvePower(int x, int N){
    int result = 1;
    for(int i = 0; i < N; ++i){
        result *= x;
    }
    return result;
}

函数 2

int solvePower(int x, int N){
    if(N == 0)
        return 1;
    return x * solvePower(x, N - 1);
}

函数 3

int solvePower(int x, int N){
    if(N == 0)
        return 1;
    if(N % 2 == 1)
        return solvePower(x, N / 2) * solvePower(x, N / 2) * x;
    return solvePower(x, N / 2) * solvePower(x, N / 2);
}

函数 4

int solvePower(int x, int N){
    if(N == 0)
        return 1
    int tmp = solvePower(x, N / 2);
    if(N % 2 == 1)
        return tmp * tmp * x;
    return tmp * tmp;
}

1.5 递归的空间复杂度

递归的空间复杂度为每次递归的空间复杂度 * 递归深度

课堂练习

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例

输入：s = “We are happy.”

输出：“We%20are%20happy.”

作业

1. 编写一个函数，其作用是将输入的字符串反转过来

示例 1

输入：[‘h’,’e’,’l’,’l’,‘o’]

输出：[‘o’,’l’,’l’,’e’,‘h’]

示例 2

输入：[‘H’,‘a’,’n’,’n’,‘a’,‘h’]

输出：[‘h’,‘a’,’n’,’n’,‘a’,‘H’]

2. 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1

输入: s = “abcdefg”, k = 2

输出: “cdefgab”

示例 2

输入: s = “lrloseumgh”, k = 6

输出: “umghlrlose”