递归

Recursion
用函数自身来定义函数的方法，使用有限的语句来定义无限对象的集合，用于描述自相似方法、重复事物的过程。
同时是重要的思维模式，使用递归基础和递归公式/步骤两部分来定义。

“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。

递归条件（recursive case）：调用自身
基线条件（base case）：不再调用自身（避免形成无限循环）

算法层面

是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。

1. 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
2. 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

而从实现的角度看，递归代码主要包含三个要素。

1. 终止条件：用于决定什么时候由“递”转“归”。
2. 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
3. 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

调用栈

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。

• 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。
• 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。
  这种工作机制与栈的“先入后出”原则异曲同工

尾递归

Tail recursion
如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。

• 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
• 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

递归树

当处理与“分治”相关的算法问题时，递归往往比迭代的思路更加直观、代码更加易读。不断递归调用下去，最终产生递归树。

从本质上看，递归体现了“将问题分解为更小子问题”的思维范式，这种分治策略至关重要。

• 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用了这种思维方式。
• 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

原始递归函数

原始递归函数：由本原函数出发，经过有限次函数复合与递归构造的函数

1. 递归基础/本原函数

• 初始函数： $f()=Constant$
  0 元函数，常数函数
• 后继函数： $S(x)=x+1$
  1 元后继函数，接受一个参数 $x$，并返回 $x$ 的后继函数 $x+1$
• 投影函数： $P_i^n(x_1,x_2,\cdots ,x_n)=x_i$
  n 元投影函数，接受 n 个参数，返回第 i 个参数的值、

2. 递归公式

函数复合

函数递归

例子：加法的定义

add (0, x)= $P_1^1(x)$
add (S (n), x)=S ($P_1^3$ (add (n, x), n, x))

完全递归

从后向前代入，找到一条计算的路径，再由前向后一次计算