递归

递归规则在定义或执行中重新使用自身。例如计算一列数的总和，可以把首项与剩余部分的总和组合起来，再对剩余部分重复同样方法。规则既要说明如何分解，也要说明何时不再继续；空列表等基础情况，让整个过程有机会逐步收束成一个结果。

参考：[1]

写了基础情况并不能保证所有输入都会到达它。每一步需要朝适合的方向推进，例如让待处理列表缩短，或让非负计数减小。若子问题没有变小、输入违反假设，或者规则在若干状态间循环，程序仍可能永不返回。终止性是算法的性质，不是递归语法自动附带的保证。

参考：[2]

同样使用递归定义，实际过程可以保留很多待完成的操作，也可以把中间结果放进参数逐步推进。SICP用阶乘比较这两种过程：一个等待内层结果再相乘，另一个携带累积结果。尾调用支持会影响控制空间，因此不能只看函数是否调用自己就判断会占用多少栈。

参考：[1]

递归也适用于树和嵌套结构，每个分支可以继续处理自己的子结构。但若多次重新计算相同子问题，运行量可能迅速增长；缓存结果或改变分解方式会产生不同成本。递归提供的是表达结构的工具，是否高效仍取决于子问题数量、重复工作及保留数据的规模。

参考：[2]