递归存储返回值？

Question

我在理解递归时遇到了一些困难，因为在某些情况下，我认为这确实很有意义，但在另一些情况下，我很难理解。我知道递归可以帮助将问题分解为更容易解决的子问题，然后可以将这些子问题的解决方案组合起来，以获取我们要解决的主要问题的主要解决方案。例如，我们有找到n的斐波那契和的代码。当然，这不是最快的实现，因为它会导致许多重新计算。

def fib(n):
    """Assumes n is an int >= 0
    Returns Fibonacci of n"""
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

在这种情况下，我了解发生了什么情况，因为在解决基本情况之后，返回的值被存储并在后续的else语句中重复使用，也就是说，对于fib（2），fib（1）+ fib（0）将返回2 ），然后将fib（2）的结果用于计算fib（3），其中fib（3）= fib（2）+ fib（1），我们已经有了答案。这对我来说很清楚，因为最后一个基本案例（即递归调用高于基本案例）之后返回的结果被重用，最终目的是获得答案。

但是，在某些情况下，我发现递归并不是那么简单，这让我感到非常困惑。例如，我们有以下代码：

def maxVal(toConsider, avail):
    """Assumes toConsider a list of items, avail a weight
    Returns a tuple of the total weight of a solution to the
    0/1 knapsack problem and the items of that solution"""

    if toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getWeight() > avail:
    # Explore right branch only
        result = maxVal(toConsider[1:], avail)
    else:
        nextItem = toConsider[0]
    # Explore left branch
    withVal, withToTake = maxVal(toConsider[1:],
                                 avail - nextItem.getWeight())
    withVal += nextItem.getValue()
    # Explore right branch
    withoutVal, withoutToTake = maxVal(toConsider[1:],
                                       avail)
        # Choose better branch
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    return result

我没有得到的是，在调用基本情况之后，返回的结果在以后的递归调用中使用过的地方是什么？似乎下面的递归调用的结果从未与其他递归调用关联-这是真的吗？这与上面看到的斐波那契递归不同。例如，一旦达到具有toConsider = []或avail == 0的基本情况，我的结果将是（0，（）），然后返回此结果。但是如何从倒数第二倒数第二倒数第二倒数第二倒数递归中使用最后一个基本案例的结果呢？进一步推论，那么倒数第三次递归似乎与倒数第二个无关，而倒数第四次与倒数第三无关，依此类推...直到主要解决方案为止。但是当然显然不是这样。我了解代码是从表面上理解的，这意味着它准确地描述了决策树中自上而下到最后一个基本情况（或节点的叶子）正在执行的操作，如果我们得到了答案，这是有意义的无论如何。但是每次递归的结果如何得到存储了，这样最终结果将反映出在许多递归中所做的回答？

另外，是否有多种理解或观点来理解递归？斐波那契示例可以提供一个实例，其中从下到上可以看到递归来解决问题，但是决策树却提供了从上到下看问题的视角。这意味着我们沿着决策树走下去，获得每个答案，直到我们已经知道解决方案的最后一个基本案例答案为止，然后我们将所有这些答案加起来以获得所需的最终答案。它是否正确？那么这是理解递归的两种主要方法-是自下而上还是自上而下？

上面的代码来自麻省理工学院的入门计算机科学书。我目前正在独立学习计算机科学，我真的希望你们能帮助我。谢谢！：D

Answer 1

您在这里有2个问题。我会尽力回答这两个问题。

但首先 ...

让我们看一下您的斐波那契例子，但我将以更详细的方式构建它：

斐波那契示例重组

def fib(n):
    """Assumes n is an int >= 0
    Returns Fibonacci of n"""
    if n == 0 or n == 1: # Base case
         return 1

    #Non base-case    
    # RECURSION STEP -- recurse to solve a subproblem
    subProblemResult1 = fib(n-1);

    # ANOTHER RECURSION STEP -- recurse to solve a different subproblem
    subProblemResult2 = fib(n-2);

    # WORK STEP
    # use the solutions of the subproblems in some way
    # (in this case, combine them by addition)
    combineResultOfSubProblems = subProblemResult1 + subProblemResult2; 

    # return the result
    return combineResultOfSubProblems;

观察结果

我们可以更轻松地进行以下观察：

1. 有1个基本情况和1个非基本情况
2. 在非基础情况下，有3个步骤-2个递归步骤，然后是一个工作步骤
3. 仅在两个递归步骤之后（即，在解决了两个子问题之后），才进行实际计算/计算的工作步骤
4. 递归的结果以某种方式（特别是通过加法）组合在一起

（return fib(n-1) + fib(n-2)原始源代码中的语句正在执行完全相同的递归步骤和工作步骤，并以完全相同的顺序执行-只是表达得更加优雅。）

现在，谈谈您的两个问题之一...

问题1：是否有多种角度来理解递归？所有递归都是自上而下还是自下而上的？

首先，让我们确定每次递归在技​​术上都是自上而下和自下而上的-您从某种根开始，一直到一或多个叶子，然后再回到根。

有趣的问题是“工作在哪里完成？” 在某些递归中（例如Fibonacci示例），所有“真实”工作都是在备份过程中完成的，因此您将其理解为自下而上。

在另一些情况下，所有实际工作都在逐步完成。考虑一个脚本，该脚本具有大写目录及其子目录中所有文件名的功能。该函数可以：

1. 首先将当前目录中每个文件的名称大写（工作步骤），然后
2. 打开每个子目录并重复（递归步骤）（当到达的目录中没有任何子目录时，就会发生基本情况。）

实际上，此示例是递归，没有返回和使用任何结果。让我们看看您的背包示例是否正确...

问题2：在背包示例中，在调用基本案例后，返回的结果在以后的递归调用中使用过的地方是什么？

您的示例缩进不正确。这是一个更正的版本，其中一些语句稍有重新排序，而注释则更明显地标识了情况和步骤：

def maxVal(toConsider, avail):
    """Assumes toConsider a list of items, avail a weight
    Returns a tuple of the total weight of a solution to the
    0/1 knapsack problem and the items of that solution"""

    # BASE CASE
    if toConsider == [] or avail == 0:
        result = (0, ())

    # NON-BASE CASE 1
    elif toConsider[0].getWeight() > avail:
    # Explore right branch only
        #RECURSIVE STEP
        result = maxVal(toConsider[1:], avail)

    # NON-BASE CASE 2
    else:
        nextItem = toConsider[0]

        # RECURSIVE STEP 1
        # Explore left branch
        withVal, withToTake = maxVal(toConsider[1:],
                                 avail - nextItem.getWeight())

        # RECURSIVE STEP 2
        # Explore right branch
        withoutVal, withoutToTake = maxVal(toConsider[1:],
                                       avail)

        # WORK STEP
        # THIS IS WHERE THE RESULTS OF THE SUBPROBLEMS ARE BEING USED
        # Unlike Fibonacci where the results of the recursions are used
        # by simply adding them them, here we do a couple more things:

        # transform the result of the first recursive step
        withVal += nextItem.getValue()
        withToTake += (nextItem,)

        # Choose better branch:
        # Compare the (transformed) result of the first recursive step
        # with the result of the second recursive step. SELECT one
        # or the other depending on the outcome of the comparison.
        if withVal > withoutVal:
            result = (withVal, withToTake)
        else:
            result = (withoutVal, withoutToTake)

    return result

查看工作步骤。与Fibonacci示例相比，仅以更复杂的方式使用子问题的结果。

在斐波那契示例中，将结果合并。在这一步中，选择结果之一并返回。