@extends('template')

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

@section('content')

# Lab 12, Part 3: Looping recursion (w/ files)

This section of the lab introduces a new pattern: the use of a loop
within a recursive function. This pattern applies when you need to handle
some kind of sub-objects (which might themselves have more stuff inside)
but you don't know how many there will be. For example, when you're
processing directories that might have other directories in them.

**Open the `looping.py` file provided in the starter files.** You can use
the provided `test_looping.py` to test the functions from this part of
the lab.


## `countDescendants`

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

To help you understand this pattern, we've provided a working function
called `countDescendants`, and a global variable `FAMILY` that represents
a family tree. The tree is represented using lists: each person is a list
where the first entry is their name. If that person has descendants, they
are listed as sub-lists within their parent's list. Here's what the `FAMILY` variable looks like:

```py
FAMILY = [
    "Louise",
    ["Richard", ["Sarah"], ["Peter", ["Aaron"]], ["John"], ["Ross"]],
    ["Steven", ["Chris"], ["Michael", ["Mac"], ["Claire"], ["Frances"]]],
    ["Jeannie", ["Anna"], ["Claire"]],
]
```
Here is a tree representation of the FAMILY variable:
<img src='tree.png' style='max-width:600px;' role="presentation" alt="A tree represenation of the FAMILY variable, with parent Louise at the top level,
with three children at the next level: Richard, Steven and Jeannie. The third
level depicts Sarah, Peter, John and Ross as children of Richard, and Aaron as a child of Peter. The third level also shows Chris and Michael as children of Steven, and Michael has three children: Mac, Claire and Frances. Jeannie, Louise's third child, has two childre, Anna and Claire.">

This variable represents one person, Louise, who has three children, Richard,
Steven, and Jeannie. Richard has four children Sarah, Peter, John, and
Ross, of whom Peter has one child, Aaron. Steven has two children: Chris
(who has no children) and Michael, who has children Mac, Claire, and
Frances. Finally Jeannie has two children, Anna and Claire. In total,
there are 16 people represented, so if we call `countDescendants` on the
whole thing, we should get 16. On the other hand, if we call
`countDescendants` on `FAMILY[1]` (i.e., Richard), we should get 6.

For this part of the lab, to understand how `countDescendants` works,
draw the function call frames for `countDescendants(FAMILY[3])` and then
answer the following questions (click to show the answers after you've
made a guess):

<details markdown="1">
<summary markdown="1">1. How many function call frames are there?</summary>
There are a total of 3 function call frames: 1 for Jeannie, and 1 each
for Anna and Claire.
</details>

<details markdown="1">
<summary markdown="1">2. What is the "base case" for `countDescendants`?</summary>
Although there is no `if/else` like we're used to seeing in a recursive
function, there is still a base case: the function won't make any
recursive calls as long as the `familyTree` list has length 1, because in
that case, the for loop will have an empty sequence and we won't do any
iterations.

Intuitively, the number of recursive calls is equal to the number of
children, so if someone has no children, then they're a base case.
</details>

<details markdown="1">
<summary markdown="1">3. What is the result for `countDescendants(FAMILY[3])`?</summary>
The result will be 3: 1 for each person.
</details>

Now without drawing the full function call frames (but feel free to draw
an abbreviated diagram if it helps), try to answer the following
questions:

<details markdown="1">
<summary markdown="1">4. What is the result for `countDescendants(FAMILY[2])`?</summary>
The result will be 6: again it's one for each person.
</details>

<details markdown="1">
<summary markdown="1">5. How many function call frames will be created to evaluate `countDescendants(FAMILY[2])`?</summary>
Again this is 6, one per person.
</details>

<details markdown="1">
<summary markdown="1">6. If each function call frame printed the name of the person it was looking at before the loop, what would be printed for `countDescendants(FAMILY[2])`?</summary>
It would print:
```txt
Steven
Chris
Michael
Mac
Claire
Frances
```
</details>

<details markdown="1">
<summary markdown="1">7. If each function call frame printed the name of the person it was looking at **after** the loop, what would be printed for `countDescendants(FAMILY[2])`?</summary>
It would print:
```txt
Chris
Mac
Claire
Frances
Michael
Steven
```

Note that this is NOT the reverse of the order above. But it is the order
in which each function call frame returns.
</details>

## `revealHiddenFiles`

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

Now that you've seen an example of a loop within a recursive function,
it's your turn to write one. Note that **this function will not be
fruitful**. Go to the `revealHiddenFiles` function in the starter file,
and fill in the code. It should print all of the hidden files (files
whose name starts with a '.') in the target directory and any
sub-directories. It should print files and inspect sub-directories in
alphabetical order. The starter file prints an example of what the
correct result should be for the supplied `testdir` folder.


## `listHiddenFiles`

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

Can you make `revealHiddenFiles` fruitful? Go to the `listHiddenFiles`
function in the starter file and write the code for a version of
`revealHiddenFiles` which returns a list of file paths for hidden files
instead of printing them out.

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

@stop