更进一步!可视化一切递归算法!

其中最重要的一个更新是支持了递归算法的可视化,而且可视化的方式可以说是我之前系列文章所阐述的算法思想的的具体实现,我真的动手把抽象的思想给展示出来了,绝对可以帮助你更好的理解算法的本质!

在我的网站首页可以快速体验:

https://labuladong.gitee.io/algo/

https://labuladong.github.io/algo/

我先简单梳理一下我之前的文章对递归算法的阐述,然后再介绍一下这次的可视化更新为什么能帮助你更好的理解递归算法。

基础梳理

首先,我在 我的算法学习心得 中说过,算法的本质是穷举,而大家普遍认为比较难的算法,比如回溯算法、动态规划、DFS 算法等,它们的本质也是穷举,住不过需要借助递归的形式,或者说是递归的思想,来实现穷举。

关于这些比较抽象的递归算法,我在 DFS/BFS/回溯/动归算法的融会贯通 中用二叉树这种简单的基本结构把它们都穿起来了,我把二叉树系列算法分为两种解题思路:

一种是分解问题的思维模式,这种思路代表着动态规划、分治算法等;另一种是遍历问题的解题思维模式,这种思路代表着回溯算法、DFS 算法等

反过来,在用动态规划/回溯算法等比较复杂的问题时,我也会教大家用树的视角来理解算法,把递归函数理解成递归树上的一个指针,比如 回溯算法秒杀排列/组合/子集问题 中我画出了全排列问题的回溯树:

在 动态规划算法核心框架 中,我画出了斐波那契问题的递归树:

只要把递归树画出来,就可以很直观地理解这些递归算法:回溯算法就是在遍历一棵多叉树,并收集叶子节点的值;动态规划就是在分解问题,用子问题的答案来推导原问题的答案

有了这些基础,我们再来看看这次的可视化更新。

递归算法的可视化

之前的可视化功能只支持数据结构的可视化,比如说二叉树、链表、数组等。而函数的递归过程是通过递归堆栈的可视化来体现的:

而现在我可以将递归函数的递归过程抽象成递归树,并且这棵递归树会随着算法的执行动态生长,这样就可以很直观地看到递归算法的执行过程了:

而且值得一提的是,这棵递归树上每个节点的信息都是被我精心设计的

比如说对于动态规划算法这种分解问题的思路,我会把每个节点的值显示为「状态」,当递归节点对应的递归调用结束之后,该节点也会记录递归调用的结果,这样就可以很直观地理解问题是如何分解的,以及子问题的答案是如何推导出原问题的答案的。

举个具体的例子,比如说 动态规划算法核心框架 中讲的斐波那契问题,我们把fib(n)的参数n作为这个问题的「状态」,那么节点的值就是每次递归调用的这个n的值。

当整个算法结束之后,我们就可以看到这棵递归树的完整结构,鼠标移到一个节点上,还可以显示该次递归调用的具体返回值:

这样,我们就可以很直观地看到问题的分解以及通过子问题的答案是推导原问题答案的过程。

另外,你也可以直观地看到备忘录剪枝的效果,比如这是不带剪枝逻辑的斐波那契算法:

这是带备忘录剪枝逻辑的斐波那契算法:

是不是发现树上的节点明显少了很多?这就是备忘录剪枝的效果,直不直观?学习算法的门槛都给你降到这份上了,再说自己学不会,理解不了那真的是借口了吧~

当然,斐波那契这个问题很简单,我只是拿来举例方便大家理解。我的网站上的所有动态规划题目都支持了类似的可视化,因为正如前文 DFS/BFS/回溯/动归算法的融会贯通 所说,它们本质都是树。

再看看回溯算法,因为回溯算法是遍历的思路,所以我会把每个节点的值显示为「路径」,记录遍历到当前节点经过的路径。比如说 回溯算法秒杀排列/组合/子集问题 中的全排列问题,这是算法最终执行完成的样子:

可以看到,这棵递归树上的每个节点都记录了从根节点到当前节点的路径,每个叶子节点就是一个全排列的结果,和我之前画的回溯树一模一样:

其实我觉得只要画出递归树已经比较好理解了,但可视化面板是可交互的,执行到的代码会高亮显示,你可以结合着代码的执行,更直观地理解回溯算法的遍历过程。