1.7 递归函数

[giscus[bot]]

1.7 递归函数

SICP Python 中文翻译

https://composingprograms.netlify.app/1/7

[kirkzhangtech]

真的会在实际的应用中使用递归吗？

[liucheng532]

我也是上完后收获很大，改变了思考问题解决问题的思路，思维模式的改变有用

[Life-s-A-Struggle]

不太能理解分割数的算法T-T

[ciron-nine]

看成一整个集合，大集合由两个小集合（包含最大数、不包含最大数）构成，这两个小集合互斥，即两个小集合元素个数之和等于大集合元素个数之和。然后就是表达问题，求包含最大数的集合元素个数问题可以表达为：求该数减去一个最大数（最大数不变）集合元素个数问题，另一个不包含最大数的问题则表达为求该数（最大数减一）的问题。这两个问题再分别继续分割，直至为0,证明找到一种排列，小于0,则是证明该排列错误。

[zclyyt]

将 n 的所有分割方式分为两组：至少包含一个 m 的和不包含 m 的。
第一组中的每次分割都是对 n-m 的分割，然后在最后加上 m。（确保每次递减产生的数在该次分割最少含有一个）
第二组中的每次分割都是对最大数为m-1的n的分割。
两个递归——>树递归（￣︶￣）

[wangding]

跟换硬币的问题思路类似

[CharlieCRX]

简单阅读1.7的要点

首先一句话总结本节内容：用递归调用来理解“函数抽象”的概念。

所以在这里递归是工具，是为了方便更好地理解函数抽象概念的。这里面涉及到的函数抽象概念就是递归的核心问题：如何将原问题分解为同类的子问题而解决。

想要通畅阅读本节，你是需要一定的背景知识的。背景知识如下（预计背景知识准备时间：0.5-1h）：

1. 递归是什么？（思考：递归分为递推和回归，这两个过程是按照什么原则进行的？）
2. 如何实现递归？
3. 图形化执行递归函数：为了更好地理解递归的过程，将1.7材料中较为简单的递归打印函数：cascade(n)代码粘贴进去，走一遍看看效果
4. 斐波那契数列的递归应用
5. 什么是分割数？（1.7节的材料最后用分割数作为检验递归调用是否理解的范例）

带着一定的问题将上面涉及的背景知识看完，然后再通篇阅读1.7，就能明白这节讲什么了。

[wmjim]

这个补充的背景知识真好

[wangding]

递归的分类一，按递归是否直接调用自己，分为：

• 直接递归
• 间接递归（这里的互递归）

递归的分类二，按递归函数中调用自己的次数，分为：

• 线性递归
• 两路递归（这里的二叉树形递归）
• 多路递归