我正在学习递归,我已经使用递归解决了一些其他的问题,例如创建二叉树、汉诺塔等。因此,我理解什么是递归,但我发现自己在规划和实现正确的递归解决方案时有困难。
是否有任何通用的提示可以帮助我规划、思考或实现递归解决方案呢?
是否有任何通用的提示可以帮助我规划、思考或实现递归解决方案呢?
基本上,只需要考虑两件事:
您会发现,所有经典的递归算法都具备这些特性,例如二分查找、树遍历、排序/合并、阶乘计算、最大公约数计算等(a)。
如果满足这两个条件,则该问题可能适合使用递归解决。
我说“可能”,因为即使展现出这些特性的问题也并不总是适合递归,例如:
// Add two unsigned inetegers.
unsigned int add (unsigned int a, unsigned int b) {
if (a == 0)
return b;
return add (a - 1, b + 1);
}
一旦确定问题可以通过递归解决,最重要的事情之一就是确定递归算法的停止条件。一个简单的例子是计算阶乘:你知道应该在达到0或1时停止(无论你选择哪个),因此在允许递归继续之前,这应该是你在进入函数时首先检查的事情,如果你不想遇到堆栈溢出异常:
public static int factorial(int n)
{
if (n == 1)//I'm done
return 1;
return n * factorial(n - 1); //continue with the recursion
}
这基本上是我的递归方程:什么是停止条件?在进入递归函数后,将其作为第一条语句。
总之,这意味着我们必须从下往上工作;将塔在底部盘子处分割。这也意味着退化情况,即n=1,是移动顶部盘子。因此,递归算法是递归地将N-1个盘子移到一边,将第n个盘子移动到目标位置,然后将N-1个盘子移到目标位置。
如果这还不够指导,请提出更具体的问题。