数据结构与算法整理总结---递归

递归

递归是一种应用非常广泛的算法(或者编程技巧)

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
  3. 存在递归终止条件

例子:
f(n)=f(n-1)+1 其中,f(1)=1

function f($n){
    if($n == 1){
        return 1;
    }
    return f(n-1)+1;
}

如何编写递归代码?

写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条 件,最后将递推公式和终止条件翻译成代码。

递归代码要警惕重复计算

数据结构与算法整理总结---递归

若递归算法存在重复计算的情况,可通过创建一个数组,将计算结果存入数据当中,当再次需要计算时,先查看数组是否存在该值,存在直接取,不存在则运行计算。

总结

递归有利有弊,利是递归代码的表达力很强,写起来非常简洁;而弊就是空间复杂度高、有堆栈溢出的⻛险、存在重复计算、过多的函数调用会耗时较多等问题。所以,在开发过程中,我们要根据实际情况来选择是否需要用递归的方式来 实现。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!