Learn Recursion with Python: Course OverviewCourse Overview

Recursion: Python

Recursion gives you a new perspective on problem-solving by defining a problem in terms of itself.

Start

Key Concepts

Review core concepts you need to learn to master this subject

Stack Overflow Error in Recursive Function

Fibonacci Sequence

Call Stack Construction in While Loop

Binary Search Tree

Recursion and Nested Lists

Fibonacci Recursion

Modeling Recursion as Call Stack

Recursion in Python

Stack Overflow Error in Recursive Function

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Fibonacci Sequence

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Call Stack Construction in While Loop

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Binary Search Tree

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Recursion and Nested Lists

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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 Recursion

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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).

Modeling Recursion as Call Stack

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Build a Binary Search Tree

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Recursive Depth of Binary Search Tree

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Sum Digits with Recursion

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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

552 = 5 + 5 + 2 = 12

Palindrome in Recursion

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Fibonacci Iterative Function

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Recursive Multiplication

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Iterative Function for Factorials

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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.

Recursively Find Minimum in List

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
    
myfunction(1000)  #results in stack overflow error

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

Recursion: Python

Lesson 1 of 2

1
Building Our Own Call Stack
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…
Start
2
Building Our Own Call Stack, Part II
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…
Start
3
Sum to One with Recursion
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 …
Start
4
Recursion and Big O
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…
Start
5
Stack Over-Whoa!
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…
Start
6
No Nested Lists Anymore, I Want Them to Turn Flat
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 = […
Start
7
Fibonacci? Fibonaccu!
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…
Start
8
Recursive Data Structures
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…
Start

1
Rules of the Throwdown
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…
Start
2
When Fibs Are Good
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…
Start
3
Let's Give'em Sum Digits To Talk About
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…
Start
4
It Was Min To Be
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…
Start
5
Taco Cat
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…
Start
6
Multiplication? Schmultiplication!
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…
Start
7
How Deep Is Your Tree?
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…
Start

How you'll master it

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

Recursion: Python
Complete the missing piece of this recursive function which calculates the product of every number from 1 up to the integer given as an argument. this function should return 1 for an input of 0

Recursion: Python

Start

Recursion: Python

Key Concepts

Stack Overflow Error in Recursive Function

Fibonacci Sequence

Call Stack Construction in While Loop

Binary Search Tree

Recursion and Nested Lists

Fibonacci Recursion

Modeling Recursion as Call Stack

Recursion in Python

Build a Binary Search Tree

Recursive Depth of Binary Search Tree

Sum Digits with Recursion

Palindrome in Recursion

Fibonacci Iterative Function

Recursive Multiplication

Iterative Function for Factorials

Recursively Find Minimum in List

How you'll master it

Recursion: Python

Recursion: Python

Subjects

Languages