11 Recursion

identify how a problem can be broken down into smaller instances with the same structure

Strategy

1. think of the simplest input, this is usually the base case
2. try an example
3. think how if given $n$ case how do you solve $n+1$
4. generalize

Depth of a List:
maximum number sublists

[1, [2, [3, 4], 5], [6, 7], 8]

has depth 3

Nested List:
Has two types of values:
- A single integer
- A list of other nested lists ([lst_1, lst_2, ..., lst_n])
- Each sublist is a "sub-nested-list" of the outer list

this is an example of a recursive definition

Summing Up a Nested List

A function is recursive when it calls itself:

def sum_nested(obj: Union[int, list]) -> int:
	"""
	Return the sum of the numbers in a nested list <obj>.
	"""
	if isinstance(obj, int):
		# obj is an integer
		return obj
	else:
		# obj is a list of nested lists: [lst_1, ..., lst_n]
		s = 0
		for sublist in obj:
		# each sublist is a nested list
			s += sum_nested(sublist)
		return s

We will have a base case, which should be straightforward and not involve recursion. Then, we will have our recursive case. Calling the function again is a recursive function call.

Instead of attempting to trace the call, we should assume that the recursive call is correct.
This is fine if:

• The base case is correct
• Every recursive call is on a smaller input than the original.

Typical Structure:

def f(obj: Union[obj1,obj2])-> ...:
	if isinstance(obj, obj1):
		...
	else:
		for sublist in obj: 
			... f(sub_obj2) ...

Recursive functions are not more efficient than their iterative equivalent