【日撸 Java 三百行】Day 16（递归）
目录
Day 16：递归
一、关于递归
1. 什么是递归
2. 为什么是用栈来实现递归？
3. 用递归模拟解迭代方程
二、代码与测试
拓展：
小结
Day 16：递归
Task：
- 递归这个东东, 能理解的同学秒懂, 理解不了的就简直没任何办法.
- 数学式子写出来了, 直接翻译成程序, 简单方便.
- 系统会为递归建栈, 这个需要理解一下. 例如, 累加程序, 空间复杂度是O(n), 因为只有运行到 paraN = 1 时, 才会弹栈.
- Hanoi 问题虽然很有名, 但它更多的是对形参/实参的理解, 所以不写在这里给读者添堵. 再说了, 那种极端的例子也不具有代表性.
一、关于递归
1. 什么是递归
常常伴随递归出现的就是递归函数(Recursive Function)，简单来说：
就是在函数内部再次调用函数自己的过程，但是通过每次调用时携带参数的不同，从而保证每次调用都是一个全新的上下文。然后通过调用过程中的参数传递性，保证每次调用都与上一次调用存在关联性，从而实现一种逻辑上的迭代过程。
理论上，对于一切一维迭代的for循环，都可以用递归去模拟。但是反之，某些多维迭代的函数（比如DFS等）就很难使用for循环模拟，除非实现总结出转移方程，用矩阵的方式模拟出数据更新的方式，然后用动态规划的实现完成for循环。
我们用图来理解递归：
从定义上来讲，一个递归函数一定有三部分：
1). 递归入口：一般递归入口就是我们函数的调用口（例如图上的FunctionA），它是本函数的短暂停顿处，也是是下一个函数进入处。
2). 递归出口：我们的递归函数中必须要有函数的退出机制，不然我们的函数递归会把编译器分配的递归栈撑爆，陷入永无止境的进栈。这个退出口往往是对于函数的参数进行相应的判断从而终止退出的语句，简言之，就是本函数的条件退出语句。
3) 函数作用主体：一般来说，非一二即三。往往函数出口放于函数最开始，后续基本大部分内容属于函数作用主体，而函数入口放于这些主体内容之中。而函数入口往往又可以把函数作用主体分为上下两个篇章，下篇章往往可用于回溯操作。
2. 为什么是用栈来实现递归？
观察上面给的递归示意图，我们发现，一个完整的递归实际上是两段路：第一段正向传播，走到递归出口，得到整体的计算式；第二条路是从递归出口出发，返回入口，得到具体的值。从定义上来讲，我们称第二条路为回溯。
所以我们可以发现，先进后出的递归算法，与栈的存储方式完美契合。在入栈时记录具体的活动，在出栈时返回具体的值。参考下面这张示意图，可以很轻松的理解。
但这里我们需要说明的是，以上过程是计算机内部实现递归的方式，与代码没有任何关系。想要更详细的了解两者的关系，可以参考拓展部分的相关学习笔记。
3. 用递归模拟解迭代方程
数学中我们可以找到很多可以展开为递推方程的式子，而这种递推思想我们之前已经讲过for循环实现，而今天我们通过这个递推式来看下递归的设计，从而领悟递归设计的思想。
递推式的特点在于当下不知道数值的特点，但是我们知道当前环境与之前（之后）环境的关系以及某个知道数值的特殊情况。这是个很典型的递归。
用阶层计算来举例：
给出求N的阶层函数f(N)。现在我不知道这个值的具体情况，但是有一点我清楚就是：
f(N) = N * f(N-1)
解释：我们把当前求N的任务交给了N-1，实现了状态的转移（其实动态规范也是这样的递归思路）
然后进一步，代入f(N-1) = (N-1) * f(N-2)到上式有：
f(N) = N * (N-1) * f(N-2)
又因为我们知道特例f(1) = 1
于是乎可以有全部迭代的展开式：
f(N) = N * (N-1) * (N-2) * (N-3) * … * 3 * 2 * f(1)
似乎到这一步我们已经可以设计for循环了，但若要设计递归的话，这里还要加入回溯实现。
这里我们规定：若是一个常数与f()相乘，那么还要继续展开，直到出现常数与常数相乘，便从括号内向外逐步化简（回溯）
这里我们用个数举例，假如N = 6，那么我可以把迭代式成下面这个形式：
=>f(6)
=> 6 * f(5)
=> 6 * (5 * f(4))
=> 6 * (5 * (4 * f(3)))
=> 6 * (5 * (4 * (3 * f(2))))
=> 6 * (5 * (4 * (3 * (2 * f(1)))))
=> 6 * (5 * (4 * (3 * (2 * 1))))
=> 6 * (5 * (4 * (3 * 2)))
=> 6 * (5 * (4 * 6))
=> 6 * (5 * 24)
=> 6 * 120
=> 720
变得越来越长的就是深入调用，变得越来越少的就是回溯，这就是一个递归的全过程。
综上，按照我们提到的递归函数中的三个部分思想来设计有：
public static int FunctionA(int N) {if (N == 1) { // 1.递归出口return 1;} // Of if// 2.函数作用主体（前篇）int value = N;// 3.递归入口int before = FunctionA(N - 1);// 2.函数作用主体（后篇：回溯）value = value * before;return value;}// Of FunctionA
当然，更常见的递归写法，是在 return 语句中实现函数主体的递推式。
public static int FunctionA(int N) {if (N == 1) { // 递归出口一般无法简化return 1;} // Of ifreturn N + FunctionA(N- 1);}// Of FunctionA
二、代码与测试
这里，我们会展示如何用递归来实现 Fibonacci 数列。
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
package datastructure;/*** Recursion. A method can (directly or indirectly) invoke itself. The system* automatically creates a stack for it.** @author: Changyang Hu joe03@foxmail.com* @date created: 2025-05-15*/
public class Recursion {/*** ********************** @Title: sumToN* @Description: Sum to N. No loop, however a stack is used.** @param paraN The given value.* @return The sum.* @return int **********************/public static int sumToN(int paraN) {if (paraN <= 0) {// Basis.return 0;} // Of ifreturn sumToN(paraN - 1) + paraN;}// Of sumToNpublic static int fibonacci(int paraN) {if (paraN <= 0) {// Negative values are invalid. Index 0 corresponds to the first element 0.return 0;}if (paraN == 1) {// Basis.return 1;} // Of ifreturn fibonacci(paraN - 1) + fibonacci(paraN - 2);}// Of fibonacci/*** ********************** @Title: main* @Description: The entrance of the program.** @param args Not used now.* @return void **********************/public static void main(String args[]) {int tempValue = 5;System.out.println("0 sum to " + tempValue + " = " + sumToN(tempValue));tempValue = -1;System.out.println("0 sum to " + tempValue + " = " + sumToN(tempValue));for (int i = 0; i < 10; i++) {System.out.println("Fibonacci " + i + ": " + fibonacci(i));} // Of for i}// Of main}// Of class Recursion
拓展：
栈与递归：【数据结构】栈-CSDN博客
小结
从上面的案例中也能看到了，我们的递归设计思想与一般的循环设计思想是截然不同的。
一般的循环总是从已知的地方开始循环，比如今天代码中的0到N求和，我们可以从已知的N=0开始，Fibonacci数列中从已知的N=0，N=1开始。
而递归的话我们不是先找起点和终点，而是先试着把我们的问题抽象为一种递推关系，而后从递推入手，关注于数据的转移过程。
换句话说，把一个大问题化为一个个相同的问题，然后专注于每个相同的小问题实现，当每个小问题解决了，只需要通过递归入口将其连接起来就好了，后面的问题就交给计算机了。
当然，没有事物是完美的。递归的算法具有可读性强、结构简练、正确性易证明等优点,但是在时空的开销上相对较大。为提高算法的时空效率,尤其是在某些对响应时间很敏感的实时应用环境下,或在不支持递归的程序环境中,必须将递归算法转化为非递归算法,问题才能得到有效解决。