递归实现原则

2018-09-25 本文已影响216人 QiShare

级别：★☆☆☆☆
标签：「递归」「四条递归实现基本原则」
作者：陈彬
审校： QiShare团队

引言：这篇文章主要讲述递归实现原则。为了方便理解，每个原则都会对应的段代码实例。

一、定义：

目前我查到的资料中关于递归解释有两种：

程序调用自身的编程技巧称为递归。（源于知识丰厚的度娘）
当一个函数用它自己来定义时就称为是递归。（源于数据结构与算法分析书籍）

第一种说法比较直接的描述了递归在程序的实现，具体实现见下面实现原则暂不赘述，而第二种说法偏向于算法，利用数学知识更方便理解，如函数F(X)=2F(X-1)+X。

二、四条实现基本原则：

1. 基准情形：

必须总有某些基准情形，它无需递归就能解除。如求斐波那契数，输入1无需递归直接返回1，见图1-1：

图1-1

如若无基准情形传入1后，由于非负数整数X-2操作会导致越界，产生超大数，该超大数还会继续进行求斐波那契数操作，由于栈大小远小于该超大数最终会发生栈溢出问题。假如栈足够大能包容超大数量函数调度，求斐波那契数会从超大数再到0，形成循环。运行结果见图1-2。

图2-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。

图2-1

图2-2

3. 设计原则：

假设所有的递归调用都能运行。以上面求斐波那契数为例，假如求2000000的斐波那契数，由于递归函数调用次数过多，超过了分配的栈大小，导致栈溢出，见图3-1。所以从理论上讲，上面的求斐波那契数函数递归实现不符合设计法则。之前永旺同学已写过一篇关于尾递归优化文章，相关内容见：iOS objc_msgSend尾调用优化机制详解。或者将求斐波那契数递归实现转换成for循环求值，见图3-2。

PS:求2000000的斐波那契数只是为了说明这个原则，其实2000000的斐波那契数早已经超过了NSUInteger的上限了，手动滑稽。

图3-1

图3-2

4. 合成效益原则：

在求解一个问题的同一实例时，切勿在不同的递归调用中做重复工作。以第三条原则中递归方式求斐波那契数函数为例，求5的斐波那契数，在递归过程中的函数调用详情见图4-1，其中好多工作是重复的。这些重复性工作同样会消耗系统资源，增加运行时间。例如以第三条原则中递归方式求40的斐波那契数时，大概耗时2秒见图4-2，若以for方法求40的斐波那契数，耗时0.0002秒见图4-3，差距显而易见。