递归

递归

递归是，从原问题出发，逐步缩小问题规模，缩小到已知边界，回溯求解的过程。

我们以 \(1+2+3+..+n\) 的问题为例，逐渐缩小问题规模，缩小到已知边界，回溯求解的过程

int f(int n) {
    if (n == 1) return 1;

    return f(n - 1) + n;
}

我们以f(5)的执行过程为例，进行分析

代码框架

// 问题的边界

// 求解子问题

int f(int n) {
    // 问题的边界
    if (n == 1) return 1;

    // 求解子问题
    return f(n - 1) + n;
}

自己调用自己

从代码角度上看，一个函数，如果自己调用了自己，那就是递归函数。