# 7.5 Writing Recursive Functions: Using a Set of Test Scenarios

A variation on the approach we just saw is to
think in terms of a set of scenarios.
We'll record these in a table, with one row for each scenario,
as you would if you were designing a test suite.
Ultimately, we will think through a thorough set of scenarios,
but we can start with just those that are suggested by
the recursive structure of the problem.

Here is our design recipe:

1. Create one row in the table for each scenario suggested by the recursive structure of the problem. <!-- For example, consider a nested list. Since is either a simple integer or a list containing nested sublists (by definition), these are our first two scenarios for the table. -->
2. For each case that is so simple that no recursion is called for, write down what the function should do (what it should return and/or mutate).
3. For each case that is complex enough that one or more recursive calls will help:
   - Write down what recursive call(s) should be made, and **use the docstring of the function** to determine what each will do (what it will return and/or mutate).
   - Write down what the present call needs to do with those results to accomplish its goal.
4. Add to the table any other scenario(s) that you feel are important to think through, along with a concrete example. For each,
	- If it can be handled using the strategy of any previous scenario, record that fact. We won't need code for this specific case!
	- If not, handle the novel scenario as per steps (2) and (3) above.

<!--
1. Think through all possible inputs to the function and identify interesting cases, just as you would if you were designing a test suite.
2. For each case that is so simple that no recursion is called for, write down what the function should do (what it should return and/or mutate).
3. For each case that is complex enough that one or more recursive calls will help:
   1. Write down a concrete example of the input to the function.
   2. Write down what recursive call(s) will be made, and **use the docstring of the function** to determine what each will do (what it will return and/or mutate).
   3. Write down what the present call needs to do with those results to accomplish its goal.
4.
5. Review the cases to see if they can be collapsed. Sometimes two cases are handled by doing the same thing.

One way to record the analysis is in a three-column table with
one row per case.
The first column shows the case with a concrete example,
the second column shows the recursive calls needed for that case
(as well as the result of each),
and the third column shows what the present call must do.
-->

As an example, suppose we want to design this function:
```python
def flatten(obj: int | list) -> list[int]:
    """Return a (non-nested) list of the integers in <obj>.

    The integers are returned in the left-to-right order they appear
    in <obj>.
    """
```

As suggested by the recursive structure of a nested list,
our first two scenarios are
a simple integer and a list containing nested sublists.
We pick an arbitrary example of each:

<img src="images/F1-crop.jpg" alt="three-column table" width="600"/>

In scenario 1, the problem is so easy that
we don't need any "help" from a recursive call. We can simply put the given integer into
a list and return that.
It's easy to see that this strategy would work for any integer.
We record this strategy in the table:

<img src="images/F2-crop.jpg" alt="three-column table" width="600"/>

For scenario 2, we have chosen an non-trivial example of a list input.
This will help us to ensure our solution in this case is as general as possible,
in other words,
that it will handle lots of different list inputs.
First, we write down the recursive call(s) that should be made.
Since this is a list of nested lists,
all of which could contribute to the result for `flatten`,
we will need to recurse on each of them.
Then we **use the docstring of the function** to determine what each will do
(what it will return and/or mutate).
We record this in the middle column of the table:

<img src="images/F3-crop.jpg" alt="three-column table" width="600"/>

Assuming each recursive call works properly,
what does *our* call have to do in order to return the correct answer?
It's fairly easy to see that we need to put those individual results together into a
single list and return it.
We can start out with an empty list, and after each recursive call, add in its result.
(We'll need to think about whether `append` or `extend` is the right list method to use, but
that is a minor detail.)
We record this in the third column:

<img src="images/F4-crop.jpg" alt="three-column table" width="600"/>

We might think of a couple of additional scenarios, as shown here:

<img src="images/F5-crop.jpg" alt="three-column table" width="600"/>

The empty list, however, is already handled by our solution to scenario 2.
In this case, we'll start with an empty list, iterate 0 times, and
return that empty list---which is correct!
Thinking through an example of a list of integers,
we can see that this is also already handled by scenario 2!
Here is our complete table of scenarios, with these observations included:

<img src="images/F6-crop.jpg" alt="three-column table" width="600"/>



<!--
We might come up with this analysis:
<img src="images/table.jpg" alt="three-column table" width="600"/>

In scenario 1, the input is an integer. This instance of the problem is so easy that
we don't need any "help" from a recursive call. We can simply put the given integer into
a list and return that.
It's easy to see that this strategy would work for any integer.

In scenario 2, we begin to consider a list input, and we start with the simplest possible list:
an empty list.
Here again, the problem is so easy that we don't need to make any recursive calls.
There *are* no integers in this nested list,
so we can simply return the empty list.

In scenario 3, we consider a list that is 1 level deeper.
The example list we chose has 3 items.
We can see that each item is simply an integer, but the code we write won't "know" that
unless it checks.
We could iterate through the list and check each item to see if it is an integer,
but then what if some of them are and some of them aren't?
This is getting complicated, so let's see if we can bring in recursion to make our work easier!
We can ask ourselves:

- What recursive call(s) could we make on simpler instances of this problem?
- Can we use their results to solve our problem?

We could recurse on each item in the list.
And let's use partial tracing
to save the effort of thinking about how the recursive calls will work, since
all we need to know is what they'll do if they work correctly.
In the middle column of the table,
we've written
the argument we'll pass to each recursive call, and
what the function will return in each case.
Assuming that happens, what does *our* call have to do in order to return the correct answer?
It's fairly easy to see that we need to put those individual results together into a
single list and return it.
We can start out with an empty list, and after each recursive call, add in its result.
(We'll need to think about whether `append` or `extend` is the right list method to use, but
that is a minor detail.)

In scenario 4, we consider a deeper list.
Again, we wrote in the middle column the recursive calls and what they'll return
(assuming they work correctly).
The steps we laid out for scenario 3 will handle scenario 4 too!
So we can collaps these two scenarios into one branch of code.

Looking back at the other rows, you may notice that these same steps will also work
for scenario 2: In this case, we'll start with an empty list, iterate 0 times, and
return that empty list -- which is correct.
We can't, however, use those steps to handle scenario 1:
if we are passed an integer, attempting to iterate over it will generate an error.

Notice that the effort to write this table is not very great.
It requires thinking about scenarios, which you are used to from learning how to test code.
(And you can re-use these scenarios when writing your test suite.)
It requires using the same kind of recursive thinking that you have become used to
from doing partial tracing.
We also used some simple reasoning to collapse cases.
That last step isn't strictly necessary in order to get a working recursive function,
but it does produce simpler code, which is always preferable.
-->


When we translate our analysis into code,
we'll only need to implement the first two rows.
With all of our previous work, doing so is quite simple:

```python
def flatten(obj: Union[int, list]) -> List[int]:
    """Return a (non-nested) list of the integers in <obj>.

    The integers are returned in the left-to-right order they appear
    in <obj>.
    """
    if isinstance(obj, int):
        return [obj]
    else:
        s = []
        for sublist in obj:
            s.extend(flatten(sublist))
        return s

```

Then to test our code,
we can take advantage of all four scenarios
to check that our function works correctly.
If our reasoning was correct, all tests *will* pass successfully.
The purpose of testing them anyway is to check that reasoning!
Here we can see that our function indeed works correctly in all four scenarios:

```python
>>> flatten(6)
[6]
>>> flatten([[0, -1], -2, [[-3, [-5]], 4]])
[0, -1, -2, -3, -5, 4]
>>> flatten([])
[]
>>> flatten([8, 13, -2])
[8, 13, -2]
```

An interesting question is how we should record these tests.
Should they be doctests or unit tests run with pytest?
Remembering that the purpose of doctests is to communicate to the reader
what the correct behaviour of the function looks like,
we might put only the first two scenarios into doctests.
The rest are better suited to unit tests in a separate file, where we do our most thorough testing.