Dazbo's Advent of Code solutions, written in Python

Recursion (Wikipedia)Recursion Introduction (@ RealPython)

I have to admit, I used to struggle with recursion. A lot of people do. It can be a bit mind-bending. But it’s a pretty simple concept and can be very useful.

In short: **a recursive function is a function that calls itself.** Thus, the code that defines the function will include a call to the same function.

As an anology, take a look at examples of recursive acronyms. See how the acronym definition includes the acronym itself!

Acronym | Definition |
---|---|

GNU | = GNU’s not Linux |

LAME | = LAME Ain’t an MP3 Encoder |

YAML | YAML Ain’t Markup Lanugage |

Typical use cases include:

- Any time you need to calculate the
*next*value of something, based on the*current*value of something. - To traverse some sort of tree or nested structure.

We’ll look at example of these in a bit.

When creating a recursive function, there are only two rules you need to know:

- The function must have an
*exit condition*, called the*base case*. You need this, otherwise your recursive function will never end! - Each recursive call should move us closer to the base case.

We want to create recursive function that counts down from an arbitary number `n`

to 0. We can do it like this:

```
def countdown(n):
print(n)
if n == 0:
return # Terminate recursion
else:
countdown(n - 1) # Recursive call, one closer to the base case
```

As per the rules:

- We’ve defined a base condition. I.e. when we get to 0, we exit.
- We’ve defined a condition that always moves us closer to the base condition. In this case, by decrementing the value of
`n`

each time by 1.

We can simplify this code:

```
def countdown(n):
print(n)
if n > 0:
countdown(n - 1) # Recursive call, one closer to the base case
```

Let’s try it. I’ve added the above code to a file called scratch.py, in my snippets folder. I’ll now execute it from the Python REPL:

```
>>> from snippets.scratch import *
>>> countdown(5)
5
4
3
2
1
0
```

Recall the defition of factorial:

\(k! = k * (k-1)\)

This is slightly tricker than the previous example, since we’re not just printing a value with each iteration. Instead, we’re always multiplying the current iteration by the result of the previous iteration.

So we can code it like this:

```
def factorial(n):
return 1 if n <= 1 else n * factorial(n - 1)
```

- The base condition is when
`n == 1`

. In this situation,`factorial`

should always return 1. - If not the base condition, we always multiply by a recursive call where
`n`

is decremented by 1.

Note that it’s common for any recusive function that calculates a *product* to have an exit condition that returns 1.

We can see how function works by adding some debugging statements:

```
def factorial(n):
print(f"factorial() called with n = {n}")
return_value = 1 if n <= 1 else n * factorial(n -1)
print(f"-> factorial({n}) returns {return_value}")
return return_value
```

Let’s run it from the REPL:

```
>>> from snippets.scratch import *
>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24
```

Note how each `return`

is the product of `n`

and the previous return value.

Here we create a recursive function that counts all the individual elements in a list. If the list is nested, the function recurses into each *sub* list, adding the elements of that list to the overall count.

```
def count_leaf_items(item_list):
"""Recursively counts and returns the number of leaf items
in a (potentially nested) list. """
count = 0
for item in item_list:
if isinstance(item, list): # if the element is itself a list, recurse...
count += count_leaf_items(item)
else: # count the item
# this is the exit condition, i.e. when we've reached a leaf (element) rather than a nested list
count += 1
return count
```

Let’s try this…

```
nested_list = [2, [3,5], [[10,20],30]]
print(nested_list)
res = count_leaf_items(nested_list)
print(res)
```

Output:

```
[2, [3, 5], [[10, 20], 30]]
6
```

The Fibonacci sequence is an infinite sequence that generates the next number by adding the two preceding numbers.

`1, 1, 2, 3, 5, 8, 13, 21...`

I.e. to determine the `nth`

value in the sequence:

\(f(n) = f(n-2) + f(n-1)\)

The base case is where `n`

is `1`

, which returns a value of `1`

.

```
def fib(num: int) -> int:
""" Recursive function to determine nth value of Fibonacci sequence.
I.e. 1, 1, 2, 3, 5, 8, 13, 21...
fib(n) = fib(n-2) + fib(n-1)
Args:
num (int): value of n, i.e. to determine nth value
Returns:
int: The nth value of the Fibonacci sequence
"""
if num > 2:
return fib(num-2) + fib(num-1)
else:
return 1
while True:
try:
input_val = input("Enter the value of n, or q to quit: ")
if input_val.upper() == "Q":
break
print(fib(int(input_val)))
except ValueError as err:
print("Invalid input")
```

Note: this isn’t a particularly efficient function. It doesn’t scale well!

- Recursively process json - 2015 day 12
- Recursive string replacement - 2021 day 14
- Various recursinos as methods of a class - 2021 day 16
- Recursive snail mail - 2021 day 18
- Recursive game states using dynamic programming and lru cache - 2021 day 21
- Recursive directory listing by extending the list - 2022 day 7
- Recursive
`__lt__`

compare - 2022 day 13