## Key Concepts

Review core concepts you need to learn to master this subject

### Call Stack Construction in While Loop

A call stack with execution contexts can be constructed using a `while` loop, a `list` to represent the call stack and a `dictionary` to represent the execution contexts. This is useful to mimic the role of a call stack inside a recursive function.

### Modeling Recursion as Call Stack

One can model recursion as a `call stack` with `execution contexts` using a `while` loop and a Python `list`. When the `base case` is reached, print out the call stack `list` in a LIFO (last in first out) manner until the call stack is empty.

Using another `while` loop, iterate through the call stack `list`. Pop the last item off the list and add it to a variable to store the accumulative result.

Print the result.

### Recursion in Python

In Python, a recursive function accepts an argument and includes a condition to check whether it matches the base case. A recursive function has:

• Base Case - a condition that evaluates the current input to stop the recursion from continuing.
• Recursive Step - one or more calls to the recursive function to bring the input closer to the base case.

### Stack Overflow Error in Recursive Function

A recursive function that is called with an input that requires too many iterations will cause the call stack to get too large, resulting in a stack overflow error. In these cases, it is more appropriate to use an iterative solution. A recursive solution is only suited for a problem that does not exceed a certain number of recursive calls.

For example, `myfunction()` below throws a stack overflow error when an input of 1000 is used.

### Recursion and Nested Lists

A nested list can be traversed and flattened using a recursive function. The base case evaluates an element in the list. If it is not another list, the single element is appended to a flat list. The recursive step calls the recursive function with the nested list element as input.

### Fibonacci Sequence

A Fibonacci sequence is a mathematical series of numbers such that each number is the sum of the two preceding numbers, starting from 0 and 1.

### Fibonacci Recursion

Computing the value of a Fibonacci number can be implemented using recursion. Given an input of index N, the recursive function has two base cases – when the index is zero or 1. The recursive function returns the sum of the index minus 1 and the index minus 2.

The Big-O runtime of the Fibonacci function is O(2^N).

### Binary Search Tree

In Python, a binary search tree is a recursive data structure that makes sorted lists easier to search. 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 it’s parent.

### Build a Binary Search Tree

To build a binary search tree as a recursive algorithm do the following:

``````BASE CASE:
If the list is empty, return "No Child" to show that there is no node.

RECURSIVE STEP:
1. Find the middle index of the list.
2. Create a tree node with the value of the middle index.
3. Assign the tree node's left child to a recursive call with the left half of list as input.
4. Assign the tree node's right child to a recursive call with the right half of list as input.
5. Return the tree node.

``````

### Iterative Function for Factorials

To compute the factorial of a number, multiply all the numbers sequentially from 1 to the number.

An example of an iterative function to compute a factorial is given below.

### Fibonacci Iterative Function

A Fibonacci sequence is made up adding two previous numbers beginning with 0 and 1. For example:

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

A function to compute the value of an index in the Fibonacci sequence, `fibonacci(index)` can be written as an iterative function.

### Sum Digits with Recursion

Summing the digits of a number can be done recursively. For example:

``````552 = 5 + 5 + 2 = 12
``````

### Recursively Find Minimum in List

We can use recursion to find the element with the minimum value in a list, as shown in the code below.

### Palindrome in Recursion

A palindrome is a word that can be read the same both ways - forward and backward. For example, abba is a palindrome and abc is not.

The solution to determine if a word is a palindrome can be implemented as a recursive function.

### Recursive Multiplication

The multiplication of two numbers can be solved recursively as follows:

``````Base case: Check for any number that is equal to zero.
Recursive step: Return the first number plus a recursive call of the first number and the second number minus one.
``````

### Recursive Depth of Binary Search Tree

A binary search tree is a data structure that builds a sorted input list into two subtrees. The left child of the subtree contains a value that is less than the root of the tree. The right child of the subtree contains a value that is greater than the root of the tree.

A recursive function can be written to determine the depth of this tree.

1. 1
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 algo…
2. 2
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 funct…
3. 3
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 …
4. 4
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, re…
5. 5
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 th…
6. 6
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. nested_planets = […
7. 7
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 fun…
8. 8
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 reference…
1. 1
This lesson will provide a series of algorithms and an iterative or recursive implementation. Anything we write iteratively, we can also write recursively, and vice versa. Often, the difference i…
2. 2
Nice work! We’ll demonstrate another classic recursive function: fibonacci(). fibonacci() should return the Nth Fibonacci number, where N is the number given as input. The first two numbers of a F…
3. 3
Fantastic! Now we’ll switch gears and show you an iterative algorithm to sum the digits of a number. This function, sum_digits(), produces the sum of all the digits in a positive number as if the…
4. 4
We’ll use an iterative solution to the following problem: find the minimum value in a list. def find_min(my_list): min = None for element in my_list: if not min or (element < min): m…
5. 5
Palindromes are words which read the same forward and backward. Here’s an iterative function that checks whether a given string is a palindrome: def is_palindrome(my_string): while len(my_string…
6. 6
All programming languages you’re likely to use will include arithmetic operators like +, -, and . Let’s pretend Python left out the multiplication, , operator. How could we implement it oursel…
7. 7
Binary trees , trees which have at most two children per node, are a useful data structure for organizing hierarchical data. It’s helpful to know the depth of a tree, or how many levels make up t…

## How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory 