recursion - 在纸上进行递归的简单方法？

Question

我正在准备计算机科学 AP 考试，并将递归作为主题之一。作为编程新手，我想知道是否有任何简单的方法，或者您想提供一些有关递归的技巧。在考试中，我们无法使用计算机(显然)。那么找到递归解决方案的简单方法是什么？例如，以下是我书中直接出现的问题。

public static int mystrey(int x)
{
    if(x == 0)
    {
        return 0;
    } 
    else
    {
        return (x + mystrey(x/10)+mystrey(x/4);
    }
} 

如果调用 mystrey(10)，返回值是多少？

Answer 1

好吧，如果您使用递归，那么了解该函数的含义是很好的。这对理解为什么该方法是递归的很有帮助。此外，在纸上计算函数主要是通过一种称为"dispatch"的方法来完成的。在这种情况下，您会看到 mystrey(0) = 0 (如果情况)。

如果您想计算 mystrey(10) 的值，您知道它是 10、mystrey(1) 和 mystrey(2) 的总和。

您只需创建一个可以放置的表:

0: 0
10: 10+f(1)+f(2)

我们现在计算具有最高参数的函数的值，所以 mystrey(2):

2: 2+f(0)+f(0)

我们知道 f(0) 的值，它已经在表中了，所以

2: 2+0+0=2

现在我们计算 f(1)=1
我们最终得出的结论是 f(10)=10+f(1)+f(2)=10+1+2=13 .

当存在大量递归时，使用表格会很有帮助。很多时候递归会导致重叠，其中必须计算具有相同参数的函数的大量次数。通过调度可以避免“分支”。人们可以将递归视为一棵树。因为 f(0)有一个固定值，称为“基本情况”，是树的叶子。其他函数值称为“分支”。计算时f(10)我们需要计算 f(1)和 f(2) ，因此可以从 f(10) 中绘制边至 f(2)和 f(1) .这样就可以重复这个过程。

此外，在大多数情况下，优秀的程序员会在算法中编写这种调度程序。这当然是通过声明一个数组并在数组中存储值并对其执行查找来完成的。

在递归理论中，递归通常由两部分组成:基本情况部分，其中某些函数调用的答案是“硬编码”的(在您的示例中是 x=0 )，以及递归部分，其中 f(x)部分内容是f(y) .通常，可以通过使用硬编码值构建初始表来使用调度，并计算特定 x 的值。通过开始填写 x 的条目在 table 上，然后工作。