引言：这篇文章主要讲述递归实现原则。为了方便理解，每个原则都会对应的段代码实例。
一、定义：
目前我查到的资料中关于递归解释有两种：
- 程序调用自身的编程技巧称为递归。（源于知识丰厚的度娘）
- 当一个函数用它自己来定义时就称为是递归。（源于数据结构与算法分析书籍）
第一种说法比较直接的描述了递归在程序的实现，具体实现见下面实现原则暂不赘述，而第二种说法偏向于算法，利用数学知识更方便理解，如函数F(X)=2F(X-1)+X。
二、四条实现基本原则：
1. 基准情形：
必须总有某些基准情形，它无需递归就能解除。如求斐波那契数，输入1无需递归直接返回1，见图1-1：
如若无基准情形传入1后，由于非负数整数X-2操作会导致越界，产生超大数，该超大数还会继续进行求斐波那契数操作，由于栈大小远小于该超大数最终会发生栈溢出问题。假如栈足够大能包容超大数量函数调度，求斐波那契数会从超大数再到0，形成循环。运行结果见图1-2。
PS：在做demo时，发现一有趣问题，我定义求斐波那契数函数参数类型是无符号整形，我传入了
-1，结果编译通过并且执行了，笑而不语。
2. 不断推进：
对于那些需要递归求解的情形，每一次递归调用都必须要是求解状况朝基准情形的方向推进。如使用函数F(X)=2*F(X-1)+X*X计算所需的值，当我输入正整数5时，它的递归推进方向是F(5)->F(4)->F(3)->F(2)->F(1)->F(0),其中F(0)是基准情形，详细见图2-1。如果我传入了-1，它的递归推进方向是F(-1)->F(-2)->F(-3)->F(-4)->F(-5)->F(-6)…->F(∞)，离基准情形越来越远最终会发生栈溢出问题。详细见图2-2。
3. 设计原则：
假设所有的递归调用都能运行。以上面求斐波那契数为例，假如求2000000的斐波那契数，由于递归函数调用次数过多，超过了分配的栈大小，导致栈溢出，见图3-1。所以从理论上讲，上面的求斐波那契数函数递归实现不符合设计法则。之前永旺同学已写过一篇关于尾递归优化文章，相关内容见：iOS objc_msgSend尾调用优化机制详解。 或者将求斐波那契数递归实现转换成for循环求值，见图3-2。
PS:求2000000的斐波那契数只是为了说明这个原则，其实2000000的斐波那契数早已经超过了NSUInteger的上限了，手动滑稽。
4. 合成效益原则：
在求解一个问题的同一实例时，切勿在不同的递归调用中做重复工作。以第三条原则中递归方式求斐波那契数函数为例，求5的斐波那契数，在递归过程中的函数调用详情见图4-1，其中好多工作是重复的。这些重复性工作同样会消耗系统资源，增加运行时间。例如以第三条原则中递归方式求40的斐波那契数时，大概耗时2秒见图4-2，若以for方法求40的斐波那契数，耗时0.0002秒见图4-3，差距显而易见。
Demo源码：GitHub
结语：递归的实现并没有想象中那么复杂,关键是牢记上述四条基本原则。一个好的递归会使程序的实现更加简单明了,选择使用递归还是其他方式解决问题,除了具体问题具体分析,还要见仁见智了。
PS：本文用斐波那契数列当做递归例子，而实际求斐波那契数列需要使用矩阵乘法的知识。
了解更多iOS及相关新技术，请关注我们的公众号：
关注我们的途径有：
QiShare(简书)
QiShare(掘金)
QiShare(知乎)
QiShare(GitHub)
QiShare(CocoaChina)
QiShare(StackOverflow)
QiShare(微信公众号)
