@extends('template')

@section('title')
    Lab 12: Fruitful recursion
@stop

@section('content')

# Lab 12, Part 2: Branching recursion

These problems demonstrate some more complex recursive patterns, because
they involve more than one recursive call. **Open the `branching.py` file in
the starter folder** to work on this part of the lab.


## Branching function call frames

<div class='partnerA'>Partner A</div>
<div class='partnerB'>Partner B</div>

Before you try to solve branching recursive problems, you need to be able
to understand how the function call frames work. Here's an example of a
fruitful recursive function that uses branching recursion:

```py
def findMax(numbers):
    """
    Returns the largest number from a list of numbers. Returns None if
    the list is empty.
    """
    if len(numbers) == 0: # No numbers -> result is None
        return None
    elif len(numbers) == 1: # One number -> that's the max
        return numbers[0]
    else:
        # Figure out where the middle of the list is
        midpoint = len(numbers) // 2
        # Get the max of the first half and the max of the last half
        maxFirst = findMax(numbers[:midpoint])
        maxLast = findMax(numbers[midpoint:])
        # If either max is None, we can't compare them; return the other one
        if maxFirst == None:
            return maxLast
        elif maxLast == None:
            return maxFirst
        # If the first max is bigger: return it, otherwise return the second
        elif maxFirst > maxLast:
            return maxFirst
        else:
            return maxLast
```

Look at the function definition above, and draw the function call frames
for a call to `findMax([3, 1, 2])` to answer the questions below (click
on each question to show the answer, but only after you've come up with a
guess).

<details markdown="1">
<summary markdown="1">
1. How many function call frames are created when evaluating
   `findMax([3, 1, 2])`, and what is the argument for each frame?
</summary>
There are a total of 5 function call frames, with the following arguments:

1. `[3, 1, 2]` (the original function call frame)
2. `[3]` (the first half of the original list)
3. `[1, 2]` (the second half of the original list)
4. `[1]` (the first half of smaller list)
5. `[2]` (the second half of smaller list)
</details>

<details markdown="1">
<summary markdown="1">
2. How many of those are base-cases, and how many are recursive?
</summary>
Three of them are base cases (the ones with length-1 lists) and two are
recursive (the original frame and the `[1, 2]` frame).
</details>

<details markdown="1">
<summary markdown="1">
3. What is the result for `findMax([3, 1, 2])`?
</summary>
3, which is the largest number in the list.
</details>


## `printCoinPossibilities`

<div class='partnerB'>Partner B</div>

Now that you've seen an example of branching recursion, try to use it to
solve this (non-fruitful) problem: The `printCoinPossibilities` function
should print all possible results of flipping a certain number of coins,
given the results of some of the flips, plus the final number of flips.
Each result it prints will be a string consisting of the letters 'h' for
heads and 't' for tails. So for example, the string `'hht'` represents
flipping heads twice followed by tails once.

Note that the function takes two arguments: a string listing results
observed so far, and an integer specifying the total number of flips to
make. The function should print all possible sequences of flips that
contain the specified total number of flips, where the first few flips
are as specified in the observed results. So for example, if the observed
results are 'ht' and the total number of flips is 3, the possibilities
are 'hth' and 'htt'. If the number of observed results is greater than or
equal to the required number of flips, the function should just print the
observed flips, even if there are more than required. So
`printCoinPossibilities('hht', 2)` would just print 'hht'. Here are more
examples:

```py
printCoinPossibilities('hht', 2) # prints 'hht'
printCoinPossibilities('hh', 3) # prints 'hhh' and 'hht'
printCoinPossibilities('', 2) # prints 'hh', 'ht', 'th', and then 'tt'
printCoinPossibilities('', 3)
# prints all 8 possibilities starting with 'hhh' and ending with 'ttt':
#   hhh
#   hht
#   hth
#   htt
#   thh
#   tht
#   tth
#   ttt
```

Note: You can use the provided `test_branching.py` file to test this
function.

Hints:

1. The base case is not just when the number of flips is 0.
2. Only the base case needs to print anything.
3. The second argument does not decrease in the recursive calls. Instead,
    the first argument gets longer.


@include('/labs/lab12/_toc')

@stop