Recursive Functions in Python

Introduction

Welcome to the mythical realm of Pythonesia, a great empire renowned for its advanced use of magical and mathematical constructs. As the realm's head royal guard, you are tasked with the defense of the empire's most treasured artifact: The Recursive Crystal. Legends claim it was crafted using an ancient code that loops within itself to create an infinite source of energy. To understand and protect this artifact better, you must master the art of recursion in Python - the very skill that was used to create it.

Your goal will be to wield the power of recursion to solve complex problems that cannot be easily solved by conventional means. By doing so, you will ensure the safety of the empire's wealth and knowledge against those who seek to misuse it. Prepare to embark on a journey through time and code, unraveling the mysteries of recursive functions.

Skills Graph

Understanding Recursion

In this step, you will learn the basic concept of recursion and how to implement it in Python. A recursive function is one that calls itself to solve a problem. The key to designing a recursive function is to ensure it has a base case, which is a condition that stops the recursion, and a recursive case, which is where the function calls itself.

Let us start by creating a simple recursive function that calculates the factorial of a number. The factorial of a number n is the product of all positive integers less than or equal to n.

Open ~/project/factorial.py in your preferred text editor and add the following code:

def factorial(n):
    if n == 0:  ## Base case
        return 1
    else:        ## Recursive case
        return n * factorial(n - 1)

## Example usage
print(factorial(5))

To run the code, use the following command:

python3 factorial.py

The expected result should be 120 as 5! = 5 * 4 * 3 * 2 * 1 = 120.

Recursion with Multiple Base Cases

Next, you will learn how to construct a recursive function with multiple base cases. Let’s create a function fibonacci in a file named fibonacci.py, which will compute the Fibonacci sequence up to the n-th number. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.

Enter the following code in ~/project/fibonacci.py:

def fibonacci(n):
    if n == 0:  ## First base case
        return 0
    elif n == 1:  ## Second base case
        return 1
    else:         ## Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2)

## Example usage
print(fibonacci(10))

Execute the code with the command:

python3 fibonacci.py

The expected output should be 55, as it is the 10th number in the Fibonacci sequence.

Summary

In this lab, we delved into the concept of recursion in Python by applying it to two different mathematical sequences. The design thought process revolved around creating an intriguing storyline that makes learning recursion fun and relevant. The tasks were scaffolded from a simpler single base case of factorials to a slightly complex scenario with multiple base cases in Fibonacci, to ensure comprehensive understanding.

By the end of the lab, you not only became adept at writing recursive functions but also absorbed the significance of base cases and the mechanics behind recursive calls. You now hold the key to utilizing recursive algorithms to solve real-world problems, a skill as valuable as the mythical Recursive Crystal of Pythonesia itself.