递归技术的最佳教学方法是什么？
递归技术的最佳教学方法是什么？
提问于 2016-11-27 12:39:51
我正在为新的程序员教授竞争性编程。
我想教递归，但我不知道什么问题是最好的教学“递归技术”。
我知道许多递归问题，比如计算阶乘、fibonacci数和求解子集和问题等等。
但我不知道新程序员是否能理解这种递归算法。
如果你对递归技术有什么好的想法，请告诉我。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-11-27 12:54:24
这是一个非常主观的问题，可能会结束，但我会回答无论如何，以帮助你。
教授递归的步骤：
- 定义：
递归是函数本身重用函数结果时的一种现象。
- 备注：
- **end sign** is the logical term which determines whether the function will use itself or not
- if there is no end sign, or the end sign is always false, then we have an **infinite recursion**, which could lead to **stack overflow**
- **indirect recursion** is the phenomenon, when a function is not directly using its result, but its result is a dependency of a function it calls
- 数学概念
- **function composition** is the phenomenon which occurs when a function calls another function example (**the example is actually not a function composition, as correctly pointed out in the comments section**): _tangent(alpha) = sin(alpha) / cos(alpha)_
- recursion is a specific case of function composition, when building the dependency tree of an f function, we can find f as a **dependency**
- 示例：
- n! (this is so simple, that we should start with this one)
- Fibonacci
- binary search
- 展示堆栈是什么，以及如何使用自己的堆栈重写递归函数以迭代。
- 证明递归并不总是最好的答案，例如Fibonacci可以用一个简单的公式来计算，它将得到O(1)中的n个数，而它的递归版本如果没有优化的话是指数的，如果优化则是线性的，更不用说大n值上可能的堆栈溢出问题了。
编辑：
正如禤浩焯科伦奇正确指出的，
切线(α)= sin(alpha) /cos(α)
并不是真正的功能组合。让我们不要把重点放在他使用的语言和风格上，也不要关注他的错误，让我们关注他的批评中的一个问题--他是对的。所以，让我们把这个例子改为这个例子：
n！=n*(n-1)！
函数调用自己的位置。
如注释部分所示，函数组合的另一个示例是：
tan(x) = div(sin(x)，sin(π/2-x))
自sin(π/2-x) = cos(x)
EDIT2：
禤浩焯在评论部分指出，有些过程和方法(取决于工作环境)不返回值，但仍然是递归的。从技术上讲，他是对的，但我仍然认为，基于功能的描述很容易理解，因此，如果它适合于功能描述，那么对这种情况的解释可能会更好。
为了使递归课可以理解，可以解释它们不是函数，它们仍然起作用并改变状态。这样，这个案子就完全符合我们的教训了。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40829042
复制相关文章
相似问题
腾讯云开发者
