递归概念与算法实现原理｜swift代码演练

递归的实现原理

递归的调用实际上是通过调用栈（callback stack）来实现的，笔者用一张图从factorial(3)开始调用到最后得出6这个顺序之间发生的事情画了出来：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

由上图可以看出，整个递归的过程和栈的入栈出栈的操作非常类似：橘黄色背景的圆角矩形代表了栈顶元素，也就是正在执行的操作，而灰色背景的圆角矩形则代表了其余的元素，它们的顺序就是当初被调用的顺序，而且在内容上保持了当时被调用时执行的代码。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

现在笔者按照时间顺序从左到右来说明一下整个调用的过程：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

• 最开始传入3之后，3满足了n>=2的条件，继续调用自己：3 * factorial(2) ，入栈。
• 传入2之后，2满足了n>=2的条件，继续调用自己：2 * factorial(1) ，入栈。
• 传入1之后，1满足了n<2的条件，停止调用自己，返回了1，出栈。
• 此时的栈顶元素为2 * factorial(1) ，而刚刚factorial(1)返回了1，所以现在这里变成了2 * 1 = 2，出栈。
• 同样地，此时栈顶元素为3 * factorial(2)里的 factorial(2)返回了2，所以现在这里变成了3 * 2 = 6，出栈。
• 最后，factorial(3)返回了6，出栈，递归结束。

按照笔者个人的理解：整个递归的过程可以大致理解为：在使递归继续的条件为false之前，持续递归调用，以栈的形式保存调用上下文（临时变量，函数等）。一旦这个条件变为true，则立即按照出栈的顺序（入栈顺序的逆序）来返回值，逐个传递，最终传递到最开始调用的那一层返回最终结果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

再简单点，递归中的“递”就是入栈，传递调用信息；“归”就是出栈，输出返回值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

而这个分界线就是递归的终止条件。很显然，这个终止条件在整个递归过程中起着举足轻重的作用。试想一下，如果这个条件永远不会改变，那么就会一直入栈，就会发生栈溢出的情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

使用递归时需要注意的问题

基于上面递归的例子，我们将递归终止条件去掉：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

func factorialInfinite(_ n:Int) -> Int{
    return n * factorialInfinite(n-1)
}

factorialInfinite(3)
复制代码

这段代码如果放在playground里，经过一小段时间（几秒钟或更多）后，会报一个运行时错误。也可以在return语句上面写一个print函数打印一些字符串，接着就会看到不停的打印，直到运行时错误，栈溢出。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

所以说在今后写关于递归的代码的时候，一定要注意递归的终止条件是否合理，因为即使条件存在也不一定就是合理的条件。我们看一下下面这个例子：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

func sumOperation( _ n:Int) -> Int {
    if n == 0 {
        return 0
    }
    return n + sumOperation(n - 1)
}

sumOperation(2) //3
复制代码

上面的代码跟阶乘类似，也是和小于当前参数的值相加，如果传入2，那么知道 n=0时就开始出栈，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

2 + 1 + 0 = 3。看似没什么问题，但是如果一开始传入 - 1 呢？结果就是不停的入栈，直到栈溢出。因为 n == 0 这个条件在传入 - 1 的时候是无法终止入栈的，因为 - 1 之后的 -1 操作都是非0的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

所以说这个条件就不是合理的，一个比较合理的条件是 n < = 0。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html

func sumOperation( _ n:Int) -> Int {
    if n <= 0 {
        return 0
    }
    return n + sumOperation(n - 1)
}

sumOperation(-1) //0
复制代码

相信到这里，读者应该对递归的使用，调用过程以及注意事项有个基本的认识了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4503.html