人生就是一场递归，那么我学习"递归"又是为了上层的哪个递归？

什么是递归？

中文解释

程序调用自身的编程技巧称为递归（recursion）

1
2
3
4
5
6

查词典。
我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。
当你查一个词，发现这个词的解释中某个词仍然不懂，
于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，
于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，
然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。。。

1
2
3
4
5

从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是
--从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是
----从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是
------从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是
--------

英文解释

循环（loop），指的是在满足条件的情况下，重复执行同一段代码。比如，while语句。
迭代（iterate），指的是按照某种顺序逐个访问列表中的每一项。比如，for语句。
遍历（traversal），指的是按照一定的规则访问树形结构中的每个节点，而且每个节点都只访问一次。
递归（recursion），指的是一个函数不断调用自身的行为。比如，以编程方式输出著名的斐波纳契数列。

1
2
3
4

Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type. 
Recursion is used in a variety of disciplines ranging from linguistics to logic.
The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.
While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

Recursion is the process of repeating items in a self-similar way.

英文的Recursion从词源上分析只是"re- (again)" + “curs- （come, happen）” 也就是重复发生，再次重现的意思。 而对应的中文翻译 ”递归“ 却表达了两个意思：”递“＋”归“。 这两个意思，正是递归思想的精华所在。从这层次上来看，中文翻译反而更达意。

递归思想之所以困难，原因在于它非常像是循环推理（circular reasoning）

辅助解释

递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。
它表现在一段程序中往往会遇到调用自身的那样一种coding策略，这样我们就可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。
递归往往能给我们带来非常简洁非常直观的代码形势，从而使我们的编码大大简化，然而递归的思维确实很我们的常规思维相逆的，我们通常都是从上而下的思维问题， 而递归趋势从下往上的进行思维。
这样我们就能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。

一般来说，递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

递归算法要求。递归算法所体现的“重复”一般有三个要求：

(1) 是每次调用在规模上都有所缩小（通常是减半）；
(2) 是相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）；
(3) 是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

递归的三大要素

第一要素：明确你这个函数想要干什么

第二要素：寻找递归结束条件

第三要素：找出函数的等价关系式

递归的缺点

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

递归的一些优化思路

1. 考虑是否重复计算

2. 考虑是否可以自底向上

跟循环的区别

递归是静中有动，有去有回。
循环是动静如一，有去无回。
递归其实和循环是非常像的，循环都可以改写成递归，递归未必能改写成循环，这是一个充分不必要的条件

尾递归(递推)

尾递归（tail recursive），看名字就知道是某种形式的递归。简单的说递归就是函数自己调用自己。那尾递归和递归之间的差别就只能体现在参数上了。
尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。
尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。
这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。
如果有尾部归递，就只需要叠套一个堆栈，因为电脑只需要将函数的参数改变再重新调用一次。
利用尾部递归最主要的目的是要优化，例如在Scheme语言中，明确规定必须针对尾部递归作优化。可见尾部递归的作用，是非常依赖于具体实现的
尾递归的本质是：将单次计算的结果缓存起来，传递给下次调用，相当于自动累积。

在Java等命令式语言中，尾递归使用非常少见，因为我们可以直接用循环解决。而在函数式语言中，尾递归却是一种神器，要实现循环就靠它了。

很多人可能会有疑问，为什么尾递归也是递归，却不会造成栈溢出呢？因为编译器通常都会对尾递归进行优化。编译器会发现根本没有必要存储栈信息了，因而会在函数尾直接清空相关的栈。

递归转循环

递归程序改用循环实现的话，一般都是要自己维护一个栈的，以便状态的回溯。
如果某个递归程序改用循环的时候根本就不需要维护栈，那其实这个递归程序这样写只是意义明显一些，不一定要写成递归形式。
但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态，以便回溯。
原理上讲，所有递归都是可以消除的，代价就是可能自己要维护一个栈。
很多情况下用递归还是必要的，它往往能把复杂问题分解成更为简单的步骤，而且很能反映问题的本质。

递归思想

递归就是有去（递去）有回（归来）。

具体来说，为什么可以”有去“？

这要求递归的问题需要是可以用同样的解题思路来回答类似但略有不同的问题。

为什么可以”有回“？

这要求这些问题不断从大到小，从近及远的过程中，会有一个终点，一个临界点，一个baseline，一个你到了那个点就不用再往更小，更远的地方走下去的点，然后从那个点开始，原路返回到原点。
递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。
在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。
另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

什么时候需要用递归？

当有些问题的定义本身就是递归形式的时候，最是适合用递归来解决。
用递归来解决这些问题，往往几行代码就搞定了一些看起来相当”吓人“的问题。
当然，递归的性能问题是另一回事，栈的分配，函数调用代价都是在具体工程实践中要考虑的。
但现在只是讨论递归思想的话，不妨先放下那些，欣赏下递归的美。