计划问题的递归解决方案的最佳方法是什么? [英] What is the best way to plan a recursive solution to a problem?

问题描述

我正在学习递归.我已经使用递归解决了其他一些问题，例如创建二叉树，河内塔等.因此，我了解了递归是什么，但是我发现自己很难计划和实施正确的递归解决方案.

I am learning about recursion. I have solved some other problems using recursion, such as creating a binary tree, Towers of Hanoi, etc. So, I understand what recursion is, but I find myself having difficulty planning and implementing a correct recursive solution.

是否有用于计划，考虑或实施问题的递归解决方案的一般性提示?

Are there any general tips out there for planning, thinking about, or implementing recursive solutions to a problem?

推荐答案

递归是关于在进程 自相似" >解决问题.一个典型的递归示例，计算正整数的阶乘可很好地说明这一过程.

Recursion is all about identifying "self-similarity" within the process of solving a problem. A typical example of recursion, calculating the factorial of a positive integer shows this process very well.

由于阶乘n!被定义为n * (n-1) * (n-2) ... * 1，因此您应该能够看到

Since factorial, n!, is defined as n * (n-1) * (n-2) ... * 1, you should be able to see that

n! = n * (n-1)!

换句话说， n的阶乘是(n-1)的阶乘的n倍" .

In other words, The factorial of n is "n times the factorial of (n-1)".

如果您能够理解该语句以及它如何表现出自相似"的行为，那么您将做好处理递归的准备. 编程递归时的关键是确定何时停止，而不执行递归调用.对于阶乘，在试图确定阶乘的数字为1时停止.结果仅定义为1，因此您将返回该值，而不是返回递归函数调用的值.

If you can understand that statement, and how it exhibits "self-similar" behavior, then you are well primed to tackle recursion. The critical thing when programming recursion is identifying when to stop, and NOT perform the recursive call. In the case of factorial, you stop when the number you are trying to determine the factorial of is 1. The result is simply defined as 1, so you return that value instead of returning the value of the recursive function call.

因此，在考虑如何递归解决问题时，我的建议是尝试确定当前问题中的这种自相似性.如果您可以轻松地识别出这种相似性，那么问题可能具有有效而优雅的递归解决方案.如果这种自相似性不明显，则可能更适合于迭代方法.

So my suggestion when thinking about how to tackle a problem recursively is to try to identify this self-similarity in the problem at hand. If you can easily identify such similarity then the problem probably has an efficient and elegant recursive solution. If such self-similarity is not evident, it is probably better suited to an iterative approach.

这篇关于计划问题的递归解决方案的最佳方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！