Recursive functions implemented in Python.

Recursion: Python

Now that we've built a mental model for how recursion is handled by Python, let's implement the same function and make it truly recursive.

To recap: We want a function that takes an integer as an input and returns the sum of all numbers from the input down to 1.

```py
sum_to_one(4)
# 4 + 3 + 2 + 1
# 10
```

Here's how this function would look if we were to write it iteratively:

```py
def sum_to_one(n):
  result = 0
  for num in range(n, 0, -1):
    result += num
  return result

sum_to_one(4)
# num is set to 4, 3, 2, and 1
# 10
```

We can think of each recursive call as an iteration of the loop above. In other words, we want a recursive function that will produce the following function calls:

```py
recursive_sum_to_one(4)
recursive_sum_to_one(3)
recursive_sum_to_one(2)
recursive_sum_to_one(1)
```

Every recursive function needs a base case when the function does not recurse, and a recursive step, when the recursing function moves towards the base case. 

Base case: 
* The integer given as input is 1.

Recursive step: 
* The recursive function call is passed an argument 1 less than the last function call.

Sum to One with Recursion


The previous exercise ended with a _stack overflow_, which is a reminder that recursion has costs that iteration doesn't. We saw in the first exercise that **every recursive call spends time on the call stack.** 

Put enough function calls on the call stack, and eventually there's no room left. 

Even when there is room for any reasonable input, recursive functions tend to be at least a little less efficient than comparable iterative solutions because of the call stack. 

The beauty of recursion is how it can reduce complex problems into an elegant solution of only a few lines of code. Recursion forces us to distill a task into its smallest piece, the base case, and the smallest step to get there, the recursive step.

Let's compare two solutions to a single problem: producing a power set. A power set is a list of all subsets of the values in a list.


**This is a really tough algorithm. Don't be discouraged!** 


```py
power_set(['a', 'b', 'c'])
# [
#   ['a', 'b', 'c'], 
#   ['a', 'b'], 
#   ['a', 'c'], 
#   ['a'], 
#   ['b', 'c'], 
#   ['b'], 
#   ['c'], 
#   []
# ]
```
Phew! That's a lot of lists! Our input length was 3, and the list returned had a length of 8. 

Producing subsets **requires** a runtime of at least `O(2^N)`, we'll never do better than that because a set of `N` elements creates a power set of `2^N` elements.

Binary, <a href="https://en.wikipedia.org/wiki/Binary_number#Binary_counting" target="_blank">a number system of base 2</a>, can represent `2^N` numbers for `N` binary digits. For example:

```py
# 1 binary digit, 2 numbers
# 0 in binary
0
# 1 in binary
1

# 2 binary digits, 4 numbers
# 00 => 0
# 01 => 1
# 10 => 2
# 11 => 3
```

The iterative approach uses this insight for a very clever solution by including an element in the subset if its "binary digit" is `1`.

```py
set = ['a', 'b', 'c']
binary_number = "101"
# produces the subset ['a', 'c']
# 'b' is left out because its binary digit is 0
```
That process is repeated **for all `O(2^N)` numbers!**

Here is the complete solution. You're not expected to understand every line, just take in the level of complexity.

```py
def power_set(set):
  power_set_size = 2**len(set)
  result = []

  for bit in range(0, power_set_size):
    sub_set = []
    for binary_digit in range(0, len(set)):
      if((bit & (1 << binary_digit)) > 0):
        sub_set.append(set[binary_digit])
    result.append(sub_set)
  return result
```
Very clever but not very intuitive! Let's try recursion. 

Consider the base case, where the problem has become so simple we can solve it without doing any work. 

What's the simplest power set possible? An empty list!

```py
power_set([])
# [[]]
```

Now the recursive step. We need to progress towards our base case, an empty list, so **we'll be removing an element from the input.** 

Examine the simplest powerset that **isn't** the base case:

```py
power_set(['a'])
# [[], ['a']]
```

A power set in the recursive step requires:

* all subsets which contain the element 
 * in this case `"a"`
* all subsets which don't contain the element
 * in this case `[]`.


With the recursive approach, we're able to articulate the problem **in terms of itself.** No need to bring in a whole number system to find the solution!

Here's the recursive solution in its entirety:

```py
def power_set(my_list):
  if len(my_list) == 0:
    return [[]]
  power_set_without_first = power_set(my_list[1:])
  with_first = [ [my_list[0]] + rest for rest in power_set_without_first ]
  return with_first + power_set_without_first
```

Neither of these solutions is simple, **this is a complicated algorithm**, but the recursive solution is almost half the code and more directly conveys what this algorithm does.

Give yourself a pat on the back for making it through a tough exercise!



Stack Over-Whoa!

Excellent job writing your first recursive function. Our next task may seem familiar so there won't be as much guidance. 

We'd like a function `factorial` that, given a positive integer as input, returns the product of every integer from 1 up to the input. **If the input is less than 2, return 1**.

For example:

```py
factorial(4)
# 4 * 3 * 2 * 1
# 24
```

Since this function is similar to the previous problem, we'll add an additional wrinkle. You'll need to evaluate the big O runtime of the function. 

Note that if this is the first time you're seeing Big O notation, this might be a bit confusing. You can learn much more about this topic in the [Asymptotic Notation section](https://www.codecademy.com/paths/computer-science/tracks/cspath-cs-102/modules/asymptotic-notation/lessons/asymptotic-notation-conceptual/exercises/intro) of the Computer Science path. That being said, it is also fine to just continue working through this course and learn more about Big O later!

With an iterative function, we would consider how the number of iterations grows in relation to the size of the input. 

For example you may ask yourself, are we looping once more for each new element in the list? 

That's linear or `O(N)`. 

Are we looping an additional number of elements in the list **for each new element in the list**? 

That's quadratic or `O(N^2)`.

With recursive functions, the thought process is similar but we're replacing loop iterations **with recursive function calls**. 

In other words, are we recursing once more for each new element in the list? 

That's linear or `O(N)`.

Let's analyze our previous function, `sum_to_one()`.

```py
sum_to_one(4)
# recursive call to sum_to_one(3)
# recursive call to sum_to_one(2)
# recursive call to sum_to_one(1)

# Let's increase the input...

sum_to_one(5)
# recursive call to sum_to_one(4)
# recursive call to sum_to_one(3)
# recursive call to sum_to_one(2)
# recursive call to sum_to_one(1)
```

What do you think? We added one to the input, how many more recursive calls were necessary? 

Talk through a few more inputs and then start coding when you're ready to move on.



Recursion and Big O

Let's use recursion to solve another problem involving lists: `flatten()`.

We want to write a function that removes nested lists within a list **but keeps the values contained.**

```py
nested_planets = ['mercury', 'venus', ['earth'], 'mars', [['jupiter', 'saturn']], 'uranus', ['neptune', 'pluto']]

flatten(nested_planets)
# ['mercury', 
#  'venus', 
#  'earth', 
#  'mars', 
#  'jupiter', 
#  'saturn', 
#  'uranus', 
#  'neptune', 
#  'pluto']
```

Remember our tools for recursive functions. We want to identify a base case, and we need to think about a recursive step that takes us closer to achieving the base case.

For this problem, we have two scenarios as we move through the list.

* The element in the list **is a list itself**.
 * We have more work to do!
* The element in the list is not a list.
 * All set!

Which is the base case and which is the recursive step?



No Nested Lists Anymore, I Want Them to Turn Flat

So far our recursive functions have all included a **single** recursive call within the function definition. 

Let's explore a problem which pushes us to use multiple recursive calls within the function definition.

Fibonacci numbers are integers which follow a specific sequence: the next Fibonacci number is the **sum of the previous two Fibonacci numbers.** 

We have a self-referential definition which means this problem is a great candidate for a recursive solution!

We'll start by considering the base case. The Fibonacci Sequence starts with `0` and `1` respectively. If our function receives an input in that range, we don't need to do any work.

If we receive an input greater than `1`, things get a bit trickier. This recursive step requires **two previous** Fibonacci numbers to calculate the **current** Fibonacci number. 


That means we need **two recursive calls** in our recursive step. Expressed in code:

```py
fibonacci(3) == fibonacci(1) + fibonacci(2) 
```

Let's walk through how the recursive calls will accumulate in the call stack:

```py
call_stack = []
fibonacci(3)
call_stack = [fibonacci(3)]
```

To calculate the 3rd Fibonacci number we need the previous two Fibonacci numbers. We start with the previous Fibonacci number.

```py
fibbonacci(2)
call_stack = [fibbonacci(3), fibbonacci(2)]
```

`fibonacci(2)` is a base case, the value of `1` is returned...

```py
call_stack = [fibbonacci(3)]
```

The return value of `fibonacci(2)` is stored within the execution context of `fibonacci(3)` while ANOTHER recursive call is made to retrieve the **second most previous** Fibonacci number...

```py
fibonacci(1)
call_stack = [fibonacci(3), fibonacci(1)]
```

Finally, `fibonacci(1)` resolves because it meets the base case and the value of `1` is returned. 
```py
call_stack = [fibonacci(3)]
```

The return values of `fibonacci(2)` and `fibonacci(1)` are contained within the execution context of `fibonacci(3)`, which can now return the sum of the previous two Fibonacci numbers.

As you can see, those recursive calls add up fast when we have multiple recursive invocations within a function definition! 

Can you reason out the big O runtime of this Fibonacci function?



Fibonacci? Fibonaccu!

Data structures can also be recursive. 

Trees are a recursive data structure because their definition is self-referential. A tree is a data structure which contains a piece of data **and references to other trees!**

Trees which **are referenced** by other trees are known as _children_. Trees which **hold references** to other trees are known as the _parents_. 

A tree can be both parent and child. We're going to write a recursive function that builds a special type of tree: a _binary search tree_.

Binary search trees:
* Reference two children **at most** per tree node. 
* The "left" child of the tree must contain a value **lesser than** its parent
* The "right" child of the tree must contain a value **greater than** its parent. 

Trees are an _abstract data type_, meaning we can implement our version in a number of ways as long as we follow the rules above. 

For the purposes of this exercise, we'll use the humble Python dictionary:

```py
bst_tree_node = {"data": 42}
bst_tree_node["left_child"] = {"data": 36}
bst_tree_node["right_child"] = {"data": 73}

bst_tree_node["data"] > bst_tree_node["left_child"]["data"]
# True
bst_tree_node["data"] < bst_tree_node["right_child"]["data"]
# True
```

We can also assume our function will receive a **sorted list of values** as input. 

This is necessary to construct the binary search tree because we'll be relying on the ordering of the list input.

Our high-level strategy before moving through the checkpoints.

**Base case**: The input list is empty
1. Return `"No Child"` to represent the lack of node
**Recursive step**: The input list must be divided into two halves
1. Find the middle index of the list
2. Store the value located at the middle index
3. Make a tree node with a `"data"` key set to the value
4. Assign tree node's `"left child"` to a recursive call using the **left half of the list**
5. Assign tree node's `"right child"` to a recursive call using the **right half of the list**
6. Return the tree node



Recursive Data Structures

The best way to understand recursion is with lots of practice! At first, this method of solving a problem can seem unfamiliar but by the end of this lesson, we'll have implemented a variety of algorithms using a recursive approach.

Before we dive into recursion, let's replicate what's happening in the call stack with an **iterative function**. 

The call stack is abstracted away from us in Python, but we can recreate it to understand how recursive calls build up and resolve.

Let's write a function that sums every number from 1 to the given input.

```py
sum_to_one(4)
# 10
sum_to_one(11)
# 66
```

To depict the steps of a recursive function, we'll use a call stack and execution contexts for each function call. 

The call stack stores each function (with its internal variables) until those functions resolve in a last in, first out order.

```py
call_stack = []
recursive_func()
call_stack = [recursive_func_1]

# within the body of recursive_func, another call to recursive_func()
call_stack = [recursive_func_1, recursive_func_2]
# the body of the second call to recursive_func resolves...
call_stack = [recursive_func_1]
# the body of the original call to recursive_func resolves...
call_stack = [] 
```

Execution contexts are a mapping between variable names and their values within the function during execution. We can use a list for our call stack and a dictionary for each execution context.

Let's get started!



Building Our Own Call Stack

In the previous exercise, we used an iterative function to implement how a call stack accumulates execution contexts during recursive function calls.

We'll now address the conclusion of this function, where the separate values stored in the call stack are accumulated into a single return value.