数据结构与算法-递归

这是我参与更文挑战的第15天，活动详情查看：更文挑战

大师 L. Peter Deutsch 说过：To Iterate is Human, to Recurse, Divine.中文译为：人理解迭代，神理解递归。毋庸置疑地，递归确实是一个奇妙的思维方式。对一些简单的递归问题，我们总是惊叹于递归描述问题的能力和编写代码的简洁，但要想真正领悟递归的精髓、灵活地运用递归思想来解决问题却并不是一件容易的事情。本文剖析了递归的思想内涵，分析了递归与循环的联系与区别，给出了递归的应用场景和一些典型应用，并利用递归和非递归的方式解决了包括阶乘、斐波那契数列、汉诺塔、杨辉三角的存取、字符串回文判断、字符串全排列、二分查找、树的深度求解在内的八个经典问题。

理解递归

简单的来说，调用自身的函数称为递归函数，这种技术称为：递归；创建递归函数，必须创建一个终止条件，防止这个函数无限期的执行下去；有可能会造成栈溢出的问题

func recurse() {
    //statements
    recurse()
}
recurse()
复制代码

下图显示了递归是如何通过反复调用自身来工作的。

在Swift中递归是如何工作的

这里写图片描述

swift 递归阶乘实现

func factorial(of num: Int) -> Int {
    if num == 1 {//终止条件
        return 1
    } else {
        print("return \(num) * factorial（\(num - 1)）")
        return num * factorial(of:num - 1) //递归必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决
    }
}
let x = 4
let result = factorial(of: x)
print("\(x) 的阶乘是 \(result)")

/**
'''
return 4 * factorial（3）
return 3 * factorial（2）
return 2 * factorial（1）
4 的阶乘是 24
'''
*/
复制代码

递归满足3个条件

一个问题的解可以分解为几个问题的解
这个问题的与分解之后的子问题，除了数据规模不一样，求解的思路是一样的
存在递归终止的条件

编写递归代码

关键点：写出递归公式，找到终止条件

参考上面：swift 递归阶乘实现

function recursion(大规模){
    if (end_condition){      // 明确的递归终止条件
        end;   // 简单情景
    }else{            // 在将问题转换为子问题的每一步，解决该步中剩余部分的问题
        solve;                // 递去
        recursion(小规模);     // 递到最深处后，不断地归来
    }
}
复制代码

递归的注意点

递归代码要警惕堆栈溢出

在实际的软件开发中，编写递归代码时，我们会遇到很多问题，比如堆栈溢出。而堆栈溢出会造成系统性崩溃，后果会非常严重

解决办法：对递归函数增加一个变量计算递归的次数，也就是最大深度的方式来解决这个问题

递归代码要警惕重复计算

为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的f(k)。当递归调用到f(k)时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。

public func f(n: Int) -> Int {
    if (n == 1) { return 1}
    if (n == 2) { return 2}
    
    // hasSolvedList可以理解成一个Map，key是n，value是f(n)
    if (hasSolvedList.containsKey(n)) {
        return hasSolvedList.get(n);
    }
    
    var ret = f(n-1) + f(n-2);
    hasSolvedList.put(n, ret);
    return ret;
}
复制代码

递归理解上还是有点难度的，这篇文章从早上写到晚上，一点点的理解和体会，参考了很多文章和博客；

其他

今天是自己学习swift的第15天，这15天涉及到的代码都是用swift编写，这个过程中不断在适应swift的带来的新语法和规范，说实话swift要学习的东西真的不少，有很多的新概念和知识体系；不管怎样很开心完成了自己的第一个15天学习计划；接下来深入到swift项目开发，争取开发一个纯swift项目；项目暂时还没有想好，有好的项目推荐也欢迎留言告诉我！

加油吧，日拱一卒！