创建递归算法

Question

我一直在关注编码Bat的当前问题：

我们有由块组成的三角形。最上面一行有1块块，下一行有2块块，下一行有3块块，依此类推。递归计算(没有循环或乘法)这样一个给定行数的三角形中的块总数。

我知道问题是什么，我也知道递归是如何工作的。例如，如果给我一个递归函数，我可以手动计算出来，并显示输出结果。

问题实际上是从给定的问题创建递归函数，比如下面这个问题。我不确定如何真正设置它并递归地完成它。当实际设置递归问题时，是否有某种规则可遵循？我只能找到展示递归如何工作的示例，而不是展示如何实际解决递归问题。任何帮助理解如何准备编写实际的递归算法的人都将不胜感激。

Answer 1

大致如下：

1. 总是查看问题，并尝试找出是否可以将其划分为相同类型的子问题。这是你可以使用递归的第一个提示。本质上，您正在寻找实际问题的较小实例/版本。

因此，递归采用自上而下的方法(从较复杂的问题到较简单的问题)。

• 当你能找到这样的情况时，你应该找出“较大的”情况和“较小的”情况之间的关系，然后你就有了递归步骤。

• 最后一件事是找出终止条件，或者是你想要停止的最小或最后的情况。

您可能知道这一点，但如果不知道，它可能会对您有所帮助。

Answer 2

if(rows == 1) return 1;在这里是没用的。

对于递归全局问题，您必须拆解您的问题并找到：

1. 退出规则(可以是示例中的初始值，也可以是其中一个输入的某个退出条件)
2. 单步执行过程(要获得下一个输入，必须如何处理前一个输入)

并将它们组合到一个调用自身的函数中。

Answer 3

对于recursion算法，

首先设计base用例，对于该用例，函数应启动堆栈的展开或返回基值。

然后针对每种non-base情况设计要实际完成的算法