HoCo Hour of Code

Recursion

14pts

Python

Java

C++

Math

Algorithms

Introduction to recursion with Fibonacci numbers

Recursion is a problem-solving technique where a function calls itself (or executes code that eventually leads to calling itself). At its core, it’s a straightforward concept. However, recursion has many pitfalls. For example, this code will run infinitely until stopped by an external limitation (power, memory, terminated, stack overflow, etc.):

Python

Code:

def recursive_function():
    recursive_function()

recursive_function()

Java

Code:

public class recursiveFunctionTest{
    public static void main(String []args){
        recursive_function();
    }
     
    static void recursive_function() {
        recursive_function();
    }
}

C++

Code:

void recursive_function() {
    recursive_function();
}

int main() {
    recursive_function();

    return 0;
}

Note: Python and Java have a stack limit of ~1k and ~10k, respectively, meaning a function can only call itself 1k or 10k levels deep before your program breaks. C++ has a memory limit of ~1 MB instead of a stack limit.

Recursion is typically only used to solve problems with sub-problems. Every recursive call should bring the computer one step closer to solving the problem by breaking it down into sub-problems, and then breaking the sub-problems down into more sub-problems, until eventually the sub-problems are so simple that we know the answer. Then, once we have the solutions to the small sub-problems, we can build back up solutions to higher sub-problems until we know the solution to the original problem.

To do this, a good recursive function should have two main cases that define how it should call itself so that no stack overflows or infinite recursions occur:

Base case - This is a simple case of the problem that we know the solution of immediately. All recursive cases must reduce to a base case. Note that you can have more than one base case.
Recursive case - This is every other case of the problem. We might not know the solution to it, but we should know how to express the solution in terms of its sub-problems. This is the case where the function will call itself. Remember that eventually, all subproblems should reduce to the base case.

The flow of a recursive function that uses the two cases must be:

First, check if we have reached a base case. If we have, then return the base case solution. If we haven’t, proceed to the recursive case.
The recursive case is executed, and it should break down the problem into smaller pieces that will eventually all reach the base case.

Let’s look at an example where we need to find the

th Fibonacci number. The first two Fibonacci numbers are 0 and 1. Then, every subsequent number is equal to the sum of the previous two numbers. The Fibonacci sequence would then be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Because every Fibonacci number can be defined as the sum of 2 earlier Fibonacci numbers, we can treat the earlier numbers as sub-problems. So, our cases would be:

Base cases - the first Fibonacci number is 0, and the second Fibonacci number is 1
Recursive case - the
n
th Fibonacci number is the sum of the
n-1
th Fibonacci number and the
n-2
th Fibonacci number.

We know that if we keep defining a Fibonacci number in terms of the two previous Fibonacci numbers, then we define those Fibonacci numbers in terms of their two previous Fibonacci numbers, we will eventually reach the first or second Fibonacci number. So, we can write a function that tells us the

th Fibonacci number like so:

Python

Code:

def fibonacci_number(n):
    # base case 1
    if n == 1:
        return 0
        
    # base case 2
    if n == 2:
        return 1
    
    # recursive case
    return fibonacci_number(n - 1) + fibonacci_number(n - 2)
    
    
# Unit tests to make sure our code is working
print(fibonacci_number(1))
print(fibonacci_number(2))
print(fibonacci_number(3))
print(fibonacci_number(4))
print(fibonacci_number(5))
print(fibonacci_number(6))
print(fibonacci_number(7))
print(fibonacci_number(8))

Output:

> 0
> 1
> 1
> 2
> 3
> 5
> 8
> 13

Java

Code:

public class FibonacciNumbers{
    public static void main(String []args){
        // Unit tests to make sure our code is working
        System.out.println(fibonacci_number(1));
        System.out.println(fibonacci_number(2));
        System.out.println(fibonacci_number(3));
        System.out.println(fibonacci_number(4));
        System.out.println(fibonacci_number(5));
        System.out.println(fibonacci_number(6));
        System.out.println(fibonacci_number(7));
        System.out.println(fibonacci_number(8));
    }
     
    static int fibonacci_number(int n) {
        // base case 1
        if(n == 1) {
            return 0;
        }
        
        // base case 2
        if(n == 2) {
            return 1;
        }
        
        // recursive case
        return fibonacci_number(n - 1) + fibonacci_number(n - 2);
    }
}

Output:

> 0
> 1
> 1
> 2
> 3
> 5
> 8
> 13

C++

Code:

#include <iostream>

using namespace std;

int fibonacci_number(int n) {
    // base case 1
    if(n == 1) {
        return 0;
    }
    
    // base case 2
    if(n == 2) {
        return 1;
    }
    
    // recursive case
    return fibonacci_number(n - 1) + fibonacci_number(n - 2);
}

int main() {
    // Unit tests to make sure our code is working
    cout << fibonacci_number(1) << "\n";
    cout << fibonacci_number(2) << "\n";
    cout << fibonacci_number(3) << "\n";
    cout << fibonacci_number(4) << "\n";
    cout << fibonacci_number(5) << "\n";
    cout << fibonacci_number(6) << "\n";
    cout << fibonacci_number(7) << "\n";
    cout << fibonacci_number(8) << "\n";

    return 0;
}

Output:

> 0
> 1
> 1
> 2
> 3
> 5
> 8
> 13

The recursion you have seen thus far (where a function calls itself) is called direct recursion. A secondary type of recursion is indirect recursion, where a function calls some other functions that eventually lead back to calling itself.

Note: Tail recursion, where no code is executed after a function’s recursive call, often means that you don’t need to use recursion and can instead build the solution iteratively. This approach is called dynamic programming and is covered in a later article.

Recursive functions are an essential algorithmic technique, with applications everywhere from DFS (which you’ll see in a future article!) to the AP CS A exam.

You can play with all the code we've used in this article on Replit:

Python

Java

C++