Understanding Recursion - The Basics

I hate recursion. But let's try to learn it together.

Recursion is just another way to repeat a task, like a for loop. Let's break it down.

How a For Loop Works

A for loop needs three things:

1. A starting point

2. A step (increment/decrement)

3. A stopping condition

Here’s a simple example in Python to print numbers from 1 to 5:

start = 0
stop = 5
step = +1

for i in range(start, stop, step):
    print(i)

Another example: iterating through a to-do list:

arr = ["Leave home", "Get to the supermarket", "Add items to the cart", "Checkout", "Get back home"]

for i in range(0, len(arr), +1):
    print(arr[i])

Understanding the Call Stack (Before Recursion)

A call stack is like a to-do list for a program:

• It keeps track of tasks that need to be completed.

• The most recent task is at the top.

• The global task (main function) is at the bottom.

This is important to understand before diving into recursion.

Now, Let's Write a Recursive Function

Recursion is just a loop written differently.

• Starting point? 5

• Step? -1

• Stopping condition? 1

def rec(n: int, condition, step: int):
    if condition(n):  
        print(n)
        rec(n + step, condition, step)  

def condition(n):
    return n >= 1  

rec(5, condition, -1)

Thinking of Recursion as a To-Do List

Let’s apply recursion to iterate over our to-do list:

arr = ["Leave home", "Get to the supermarket", "Add items to the cart", "Checkout", "Get back home"]

def rec_arr(n: int, condition, step: int, arr):
    if condition(n, arr):  
        print(arr[n])
        rec_arr(n + step, condition, step, arr)  

def condition(n, arr):
    return n < len(arr)

rec_arr(0, condition, +1, arr)

A Simpler Way to Write It

Here's a more compact version without needing an extra function:

def rec_arr(n, arr):    
    if n >= len(arr):
        return
    print(arr[n])
    rec_arr(n + 1, arr)

rec_arr(0, arr)

Final Thoughts

• Recursion is just a different way of looping.

• Think of recursion as a to-do list that adds tasks to a stack.

• Base case (stopping condition) is key to prevent infinite recursion.

• Practice visualizing the call stack to understand recursion better.

Once you get used to it, recursion isn't so scary! 😃