我正在学习递归，我已经使用递归解决了一些其他的问题，例如创建二叉树、汉诺塔等。因此，我理解什么是递归，但我发现自己在规划和实现正确的递归解决方案时有困难。
是否有任何通用的提示可以帮助我规划、思考或实现递归解决方案呢？
是否有任何通用的提示可以帮助我规划、思考或实现递归解决方案呢？
4个回答
5
递归是指在解决问题的过程中识别出其中的“自相似”性质。一个典型的递归例子是计算正整数的阶乘，这个过程很好地展示了递归的过程。
由于阶乘n!被定义为n*(n-1)*(n-2)...*1，你应该能够看出：
n! = n * (n-1)!
换句话说，“n的阶乘等于n减1的阶乘再乘以n”。
如果你能理解这个语句，并且知道它如何表现出“自相似”的行为，那么你就已经做好了处理递归的准备。编写递归程序时，关键是要确定何时停止递归调用，而不是一直进行递归调用。在计算阶乘的情况下，当你要确定阶乘的数字是1时就可以停止了。结果就简单地定义为1，因此返回该值而不是返回递归函数调用的值。
所以，我的建议是，在考虑如何递归处理问题时，试着找出问题本身的自相似性质。如果你能轻松地找到这种相似性，那么这个问题可能有一个高效而优雅的递归解决方案。如果这种自相似性不明显，那么可能更适合采用迭代方法。
由于阶乘n!被定义为n*(n-1)*(n-2)...*1，你应该能够看出：
n! = n * (n-1)!
换句话说，“n的阶乘等于n减1的阶乘再乘以n”。
如果你能理解这个语句，并且知道它如何表现出“自相似”的行为，那么你就已经做好了处理递归的准备。编写递归程序时，关键是要确定何时停止递归调用，而不是一直进行递归调用。在计算阶乘的情况下，当你要确定阶乘的数字是1时就可以停止了。结果就简单地定义为1，因此返回该值而不是返回递归函数调用的值。
所以，我的建议是，在考虑如何递归处理问题时，试着找出问题本身的自相似性质。如果你能轻松地找到这种相似性，那么这个问题可能有一个高效而优雅的递归解决方案。如果这种自相似性不明显，那么可能更适合采用迭代方法。
- Michael Bray
1
谢谢你的建议！我理解了基本条件的概念，但你讲得真的很好。 - Jason Rae
2
基本上，只需要考虑两件事：
- 问题是否可以用相同（或类似）的问题来表达，但参数“更容易”？
- 是否存在一个明确的点，使得这个更简单的问题变得微不足道？
您会发现，所有经典的递归算法都具备这些特性，例如二分查找、树遍历、排序/合并、阶乘计算、最大公约数计算等（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);
}
现在，虽然这是一个有些有效的递归解决方案（尽管有点牵强），但当您的初始a很大时，您几乎肯定会耗尽堆栈空间。换句话说，现实世界将影响数学思想的纯洁性。
(a) 您可能会想知道为什么像上面的add和GCD或阶乘计算之间存在差异。答案通常在于每个递归调用如何快速减少“搜索空间”（所有可能结果的列表）。
例如，遍历平衡二叉树将消除大约一半的剩余搜索空间。 GCD计算执行模操作，这也相当快地减少了搜索空间。
然而，add函数并没有非常快速地减少搜索空间，这就是为什么它不适合递归的原因。
阶乘函数也不会非常快速地减少搜索空间，因为它每次递归调用时从参数中减去一个（类似于add）。
人们仍然使用它，可能是因为在递归调用数量产生影响之前，阶乘long将耗尽存储空间（64位无符号整数只能容纳约20个！）。
- paxdiablo
2
我认为你对“更简单的参数”的描述有些偏差。更好的描述可能是参数应该降低计算的复杂性。这很好地引出了你的第二点...当复杂性变得“琐碎”时，答案就很清晰（通常是硬编码的），递归的需求也被消除，从而结束递归调用。 - Michael Bray
这是一个很好的关于递归使用内存的解释。+1。 - Jason Rae
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
}
这基本上是我的递归方程：什么是停止条件？在进入递归函数后，将其作为第一条语句。
- Icarus
0
通常，你需要处理几个任务来设计一个递归算法。我将以汉诺塔问题为例，因为它非常适合这个场景。
首先，确保你能够看到问题本身的递归定义。具体而言，你需要确定整个问题如何被描述为在类似的、更小的子问题上操作加上一定量的工作。
对于汉诺塔问题，很容易证明移动大小为N的塔基本上与移动大小为N-1和单个盘子的塔相同。但是，如果不知道解决方案，很难立即确定哪个盘子应该是N+1，顶部还是底部。我们需要更多信息。
接下来，这实际上是上述问题的一个子集，就是考虑终止条件；你必须知道何时停止递归。如果在算法中忽略了这一步，你将陷入无限循环或超出数据结构的范围。
移动大小为1的塔与移动单个盘子完全相同，没有递归的理由。换句话说，移动大小为零的塔与根本不做任何事情是一样的，你可以完全跳过它。
最后，您必须确定问题定义的不变量，以指导您实际执行工作的方式。基本上归结为找到算法必须执行的事情，使得较小的子问题确实看起来像更大的问题，然后只在这些条件下递归。
汉诺塔问题的具体要求是不允许将较小的盘子放在较大的盘子上面。换句话说，您不能将一个“塔”放在比该塔底部盘子更小的盘子上。对于这个问题的更多推理将导致我们得出结论：如果我们在中间某个点上分裂塔，并将分裂点以下的盘子重新排列成任意但有效的排列，则分裂点以上的塔可以放在那些重新排列的盘子的任何一个上面，因为每个盘子都必须比分裂点处的盘子大。对于在分裂点以上重新排列盘子的情况，无法做出类似的情况；最上面的盘子上面什么也不能放。
首先，确保你能够看到问题本身的递归定义。具体而言，你需要确定整个问题如何被描述为在类似的、更小的子问题上操作加上一定量的工作。
对于汉诺塔问题，很容易证明移动大小为N的塔基本上与移动大小为N-1和单个盘子的塔相同。但是，如果不知道解决方案，很难立即确定哪个盘子应该是N+1，顶部还是底部。我们需要更多信息。
接下来，这实际上是上述问题的一个子集，就是考虑终止条件；你必须知道何时停止递归。如果在算法中忽略了这一步，你将陷入无限循环或超出数据结构的范围。
移动大小为1的塔与移动单个盘子完全相同，没有递归的理由。换句话说，移动大小为零的塔与根本不做任何事情是一样的，你可以完全跳过它。
最后，您必须确定问题定义的不变量，以指导您实际执行工作的方式。基本上归结为找到算法必须执行的事情，使得较小的子问题确实看起来像更大的问题，然后只在这些条件下递归。
汉诺塔问题的具体要求是不允许将较小的盘子放在较大的盘子上面。换句话说，您不能将一个“塔”放在比该塔底部盘子更小的盘子上。对于这个问题的更多推理将导致我们得出结论：如果我们在中间某个点上分裂塔，并将分裂点以下的盘子重新排列成任意但有效的排列，则分裂点以上的塔可以放在那些重新排列的盘子的任何一个上面，因为每个盘子都必须比分裂点处的盘子大。对于在分裂点以上重新排列盘子的情况，无法做出类似的情况；最上面的盘子上面什么也不能放。
总之，这意味着我们必须从下往上工作；将塔在底部盘子处分割。这也意味着退化情况，即n=1，是移动顶部盘子。因此，递归算法是递归地将N-1个盘子移到一边，将第n个盘子移动到目标位置，然后将N-1个盘子移到目标位置。
如果这还不够指导，请提出更具体的问题。
- SingleNegationElimination
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接