$ ls ~yifei/notes/

面试刷题总结(一) - 递归问题

Posted on:

Last modified:

递归是几乎一些算法的基础。实际上我认为算法题大致可以分为两类:递归和其他。

实际上计算机能解的唯二问题:

  1. 足够简单的问题:比如 x * x, x^0 = 1.
  2. 把复杂问题约简到简单问题:比如 x^n = x^(n/2) * x^(n/2)

分治、树、深度优先搜索等等实际上都是递归。

递归的核心思想:明白每个函数能做的事,并相信它们能够完成,千万不要试图跳进细节。

在面试的时候,如果允许写递归(一般是允许的),那一定要写递归解。

解题思路

对一个给定的问题:

  1. 确定哪些情形是基础情形,不需要再做递归。比如说:高度为 0 的树,或者 null 根节点,空字符串等。
  2. 把问题转化为规模更小的问题。
def fact(a, n):
    if n == 1:
        return a
    return a * fact(a, n-1)  # or n/2 or whatever...

def fact(a, n):
    if n == 1:
        return a
    h = fact(a, n/2)
    return h * h

好多时候,需要编写一个私有的 helper 方法,更改一下函数的签名。对于 Python 或者 JavaScript 的话,直接写一个闭包函数是最好的,也避免了全局变量。

Algorithme by Jeff Erickson

最后推荐一本神书:Algorithms by Jeff Erickson. 这本书全书都是在按照递归的思路讲解。

其它的书和文章的问题在于每个知识点似乎都是孤立的,比如说动态规划就在重点讲解状态转移方程和状态矩阵,而分治就在讲解如何用递归树计算时间复杂度等等。这种讲解方式下,每个知识点之间看不到有什么关联,往往熟悉了这个又忘了那个。实际上这些知识点都是有联系的,所谓的动态规划不过是状态空间搜索的一个巧妙转换,本质上和回溯是一致的,都是递归而已。每个技巧的内核都是一致的,只不过特异化之后有不同的表现,如果你不去抓住内核,通过一个主干把所有知识串联起来,而只看表面现象,那么永远也记不住的。

其他的书就好比盲人摸象,而这本书则是讲解的大象的骨骼结构和肌肉构造。分治和动归这些算法好比是大象的耳朵、尾巴等等部位,可以在外部摸到,而递归则是大象的骨架,虽然摸不到,但是只有画出了骨骼,才能把大象画好。

参考

  1. https://stackoverflow.com/questions/25367781/tips-on-solving-binary-tree-binary-search-tree-problems-using-recursion-java
  2. https://mp.weixin.qq.com/s/YFe9Z35CE4QWPDmPNitd4w
WeChat Qr Code

© 2016-2022 Yifei Kong. Powered by ynotes

All contents are under the CC-BY-NC-SA license, if not otherwise specified.

Opinions expressed here are solely my own and do not express the views or opinions of my employer.

友情链接: MySQL 教程站