@extends('template')

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

@section('content')

# The "Case-by-case" approach to solving recursive problems

The case-by-case method of recursive problem solving can help you to spot
recursive patterns, and does not require you to use wishful thinking. To
illustrate, we'll write a function using this method which must return a
list of numbers counting up to a peak number and then back down (so for
example, if we use 4 as the argument, the return value should be `[1, 2,
3, 4, 3, 2, 1]`)


## Step 1: Identify the base case (or cases)

For this problem, if we start counting from 1, then 1 is a reasonable
base-case, where the return value should be a list that just includes 1.
So our code would start with:

```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        return [ 1 ]
```


## Step 2: Add more complex `elif` cases until you spot a pattern

In the case-by-case recursion problem-solving method, we pretend that
instead of using recursion, we're going to solve the problem by simply
listing the correct solution for every possible input. So we can add
`elif` cases for a few more numbers:

```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        return [ 1 ]
    elif n == 2:
        return [ 1, 2, 1]
    elif n == 3:
        return [ 1, 2, 3, 2, 1]
```

So far, so good... but we clearly can't write *every* possible answer.
Still, we want to keep going until we spot an opportunity to copy-and
paste, which is already tempting: why write all those numbers when you
can copy them instead? In particular, to create the case for `n == 4`,
we'll copy the case for n == 3 and then add a 4 and an extra 3 in the
middle:


```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        return [ 1 ]
    elif n == 2:
        return [ 1, 2, 1]
    elif n == 3:
        return [ 1, 2, 3, 2, 1]
    elif n == 4:
        return [ 1, 2, 3, 4, 3, 2, 1]
```


## Step 3: Write a case using recursion to a previous case

Now, instead of copying and pasting code, we'll rely on recursion, since
by calling the function recursively with 4 as an argument, we can get a
Python value that's most of what we want for the result for `n == 5`.
Note that we only need to use recursion with arguments that will trigger
a previous case, so we know exactly what the recursion will do (no
wishful thinking required). We'll write:

```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        return [ 1 ]
    elif n == 2:
        return [ 1, 2, 1]
    elif n == 3:
        return [ 1, 2, 3, 2, 1]
    elif n == 4:
        return [ 1, 2, 3, 4, 3, 2, 1]
    elif n == 5:
        smaller = upDownList(4)
        return smaller[:4] + [5, 4] + smaller[4:]
```

Note that we used slicing here to cut apart the smaller list and we used
`+` to combine lists in order to insert our extra numbers in the middle.
Another option would have been to use the `.insert` method to insert the
extra 5 and 4. Now that we've written one recursive case, we're ready for
the next step:


## Step 4: Write a second recursive case

It's important to write a second recursive case, so that the pattern of
recursion becomes clear. This will look like:

```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        return [ 1 ]
    elif n == 2:
        return [ 1, 2, 1]
    elif n == 3:
        return [ 1, 2, 3, 2, 1]
    elif n == 4:
        return [ 1, 2, 3, 4, 3, 2, 1]
    elif n == 5:
        smaller = upDownList(4)
        return smaller[:4] + [5, 4] + smaller[4:]
    elif n == 6:
        smaller = upDownList(5)
        return smaller[:5] + [6, 5] + smaller[5:]
```

We want to pay close attention to what changes between each recursive
case, which will be important soon. However, we have one more step before
that:


## Step 5: Test it

Before you go ahead and generalize, you should test your function using
inputs that it is supposed to be able to deal with, to make sure it
works. In this case, we should test `upDownList` with 5 and 6 as
arguments. Since it works correctly, we're ready to move on...


## Step 6: Generalize the recursion

We can't keep defining `elif` cases, so we need an `else` case: a piece
of code that generalizes the cases we already have to work for any
number, using variables instead of constants. In our code so far, we can
see 5 places where things change between the cases for 5 and 6: the
recursive argument, the slice points, and the two numbers in the middle.
If we generalize each of those to be based on `n`, we get:

```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        return [ 1 ]
    elif n == 2:
        return [ 1, 2, 1]
    elif n == 3:
        return [ 1, 2, 3, 2, 1]
    elif n == 4:
        return [ 1, 2, 3, 4, 3, 2, 1]
    elif n == 5:
        smaller = upDownList(4)
        return smaller[:4] + [5, 4] + smaller[4:]
    elif n == 6:
        smaller = upDownList(5)
        return smaller[:5] + [6, 5] + smaller[5:]
    else:
        smaller = upDownList(n - 1)
        return smaller[:n - 1] + [n, n - 1] + smaller[n - 1:]
```

Now we should test it with numbers like 7 or 15 to see if we got it right.


## Step 7: Clean things up

We have a function that works for all cases now, so we're done, right?
Well, mostly, but we should get rid of any `elif` cases that we don't
need any more. In many cases, that's all of them, although in a few cases
one or two at the start may need to hang around. After cleanup and adding
some comments, we get:

```py
def upDownList(n):
    """
    Returns a list of numbers counting up from 1 to n and then down again.
    """
    if n == 1:
        # Base case: return a list with just the number 1 in it
        return [ 1 ]
    else:
        # Recursive case: create a smaller list using recursion, and then
        # slice it apart and insert the extra numbers in the middle that
        # are needed to create the full list
        smaller = upDownList(n - 1)
        return smaller[:n - 1] + [n, n - 1] + smaller[n - 1:]
```

Although it might be pretty hard to jump right to this solution without
any of the steps above, if we follow them, it's mostly straightforward to
get there: the trickiest part is step 3, where we write the first
recursive case, but that's easier than writing it with no support,
because we already wrote out a bunch of non-recursive cases that we can
rely on, without using wishful thinking.

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

@stop