递归与数学归纳法的关系

Question

bobo 老师能白话的阐述一下递归与数学归纳法的关系吗? 好多书籍 都在那这两个做联系.

Answer 1

liuyubobobo 2019-07-19 23:53:50

你看，我们在写递归的时候，就是要写递归的终止条件，和递归过程；

而数学归纳法，就是证明了基础条件以后（递归终止条件），假设n=k成立，证明n=k+1（递归过程，用f(k)解决了f(k+1)）

这儿这简直是一摸一样的。用计算机的语言说，就是“用子问题的解，解决原问题”。

比如在这一小节，我们解决了node.next的remove问题，也就可以解决node的remove问题。

如果对递归理解的不够透彻，不要着急，这个课程后续，会大量接触递归，每次接触递归，都可以体会一下，这个递归函数，是怎么“用子问题的解，解决原问题”。

在我的《玩转算法面试》课程中，还包含大量和算法设计相关的递归问题（回溯，贪心），有兴趣也可以关注。

继续加油！：）

• 提问者 RockCrazy #1

  非常感谢！