Storing returned values in recursion?

Question

I'm having some difficulty in understanding recursion, because for some cases I think it really make sense but in other cases I find it hard to comprehend. I know recursion can help to break down the problem into sub problems which would be easier to solve, and then the solutions to these sub problems can be combined to get the main solution to the main problem we're trying to solve. For instance, we have code to find the Fibonnaci sum of n. Of course, this is not the fastest implementation because it results in many recalculations.

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)

In this case, I understand what's happening because the returned value is stored and reused in the subsequent else statement after solving for the base case, that is, fib(1)+fib(0) will return 2 for the case of fib(2), then the result for fib(2) is used in the calculation of fib(3) where fib(3) =fib(2)+fib(1), for which we already have answers. This is clear to me because the result that is being returned after the last base case (i.e. recursive calls higher up than the base case) is being reused, with the ultimate goal to get the answer.

However, in certain cases, I find that recursion is not so straightforward, and this gets me really confused. For example, we have this code:

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

What I don't get is where does the returned result get ever used in the subsequent recursive call after the base case is being called? It seems that the result of the recursive calls below are never being connected with other recursive calls - is this true? That is unlike the case of the Fibonacci recursion seen above. For example, once I reached the base case of having toConsider=[] or avail==0, my result will be (0,()), and then I return this result. But how is this result from the last base case going to be used in the second last, penultimate recursion? Deducing further, then it seems like the third last recursion will have nothing to do with the second last, and fourth last recursion nothing to do with the third last, and so on...until the main solution. But of course this is obviously not the case. I understand how the code works in the superficial sense, meaning it describes exactly what is being done in a decision tree from top down, to the last base case (or the leaf of the nodes), and it make sense if we get the answer anyway. But how does the result in each recursion get stored, so that the final result will reflect that the answers done in the many recursions that have taken place?

Also, is there multiple understanding or perspectives to understand recursion? The Fibonacci example may provide an instance where recursion is seen from coming from bottom up to solve a problem, but the decision tree one instead offers the perspective of seeing things from top down. Meaning that we go down the decision tree, get every answer until the last base case answer for which we already know a solution, and then we sum up all these answers to get the final answer which we want. Is this correct? So is this two main ways of understanding recursion - from bottom up or top down?

The above codes come from an introductory computer science book by MIT. I am currently learning computer science independently, and I really hope you guys can help me out. Thank you! :D

Answer 1

You have 2 questions here. I'll try to answer them both.

But first ...

Let's take a look at your Fibonacci example, but I'll structure it a slightly more verbose way:

Fibonacci example restructured

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;

Observations

We can more easily make the following observations:

1. There is 1 base case and 1 non-base case
2. In the non-base case, there are 3 steps -- 2 recursion steps and then a work step
3. The work step, where real computation/calculation happens, is done only after both recursion steps (i.e. after both subproblems are solved)
4. The results of the recursions are combined in some way (specifically, through addition)

(The return fib(n-1) + fib(n-2) statement in your original source is doing exactly the same recursion steps and work step, and in exactly the same order -- it's just expressed more elegantly.)

Now, on to one of your two questions ...

Question 1: Are there multiple perspectives to understand recursion? Are all recursions either top-down or bottoms-up?

Firstly, let's establish that every recursion is technically both top-down and bottoms-up -- you start at some kind of root, go all the way to one or more leaves, and then come back up to the root.

The interesting question is "where does the work get done?" In some recursions (e.g. the Fibonacci example), all the 'real' work gets done on the way back up, so you understand it as bottoms-up.

In others, all real work gets done on the way down. Consider a script which has a function to capitalize the names of all files in a directory and it subdirectories. The function may:

1. first capitalize the name of each file in the current directory (WORK STEPS), then
2. open each subdirectory and repeat (RECURSIVE STEPS) (The base case occurs when a directory is reached that does not have any subdirectories.)

This example is in fact a recursion without any result that gets returned and used. Let's see if that's true of your Knapsack example ...

Question 2: In the Knapsack example, where does the returned result get ever used in the subsequent recursive call after the base case is being called?

Your example has incorrect indentation. Here's a corrected version, with some statements slightly reordered and comments to identify the cases and steps more obviously:

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

Look at the work step. The results of the subproblems are being used, just in a more complicated way than in the Fibonacci example.

In the Fibonacci example, the results are combined. In this one, one of the results is selected and returned.

Answer 2

Are you sure you have the indentation correct, the left branch needs to be indented into the else clause.

I prefer to immediately return when I can (I find it much easier to understand) rather than assigning to a result and only having one return at the end of the function, but that is matter of style. So rewriting in my preferred style with different comments, correcting the indentation and converting to handle list of ints:

def maxVal(toConsider, avail):
    if toConsider == [] or avail == 0:       # Empty return
        return (0, ())

    nextItem = toConsider[0]
    if nextItem > avail:                     # Too big can only be right
        return maxVal(toConsider[1:], avail)

    # Try with the item
    withVal, withToTake = maxVal(toConsider[1:], avail - nextItem)
    withVal += nextItem
    # Try without the item
    withoutVal, withoutToTake = maxVal(toConsider[1:], avail)

    if withVal > withoutVal:     # See which is best
        return (withVal, withToTake + (nextItem,))
    return (withoutVal, withoutToTake)

>>> maxVal([1,2,3,4,5], 10)
(10, (5, 3, 2))
>>> maxVal([2,2,2,2,2], 7)
(6, (2, 2, 2))

This is quite a common idiom, guard conditions immediately return, or try decomposing the problem. In this case, it decomposes to try packing the rest of the list using the value or try packing without using the value and see which returns the best value. It prefers results down the without list (withVal > withoutVal) - which I believe will give you the smallest result.