Python Recursion Tutorial

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until a base condition is met. It breaks a problem into smaller, simpler versions of itself.

Why Use Recursion?

Recursion helps to solve problems that can be broken down into similar subproblems. It is useful for tasks like traversing data structures (trees, graphs), factorial calculations, Fibonacci sequences, and more. It often provides clearer and shorter code than iterative solutions.

Components of Recursion

Base Case: Condition where recursion stops to avoid infinite calls.
Recursive Case: The part where the function calls itself with modified arguments.

5 Examples of Recursion with Explanation

Example 1: Factorial Calculation

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

print(factorial(5))

This function calculates factorial of n. It stops when n is 0 (base case) and otherwise multiplies n by factorial of (n-1).

Output:

120

Example 2: Fibonacci Sequence

def fibonacci(n):
    if n <= 1:
        return n  # Base cases
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # Recursive calls

for i in range(6):
    print(fibonacci(i), end=' ')

Computes Fibonacci numbers by adding the two previous Fibonacci numbers. Stops at n=0 or 1.

Output:

0 1 1 2 3 5

Example 3: Sum of a List

def sum_list(lst):
    if not lst:
        return 0  # Base case: empty list
    else:
        return lst[0] + sum_list(lst[1:])  # Recursive call

print(sum_list([1, 2, 3, 4, 5]))

Calculates sum of list elements by adding first element to sum of rest of list recursively.

Output:

Example 4: Reverse a String

def reverse_string(s):
    if s == "":
        return ""  # Base case
    else:
        return reverse_string(s[1:]) + s[0]  # Recursive call

print(reverse_string('hello'))

Reverses a string by moving first character to end after recursively reversing rest of the string.

Output:

olleh

Example 5: Nested Folder Size Sum

def folder_size(files):
    total = 0
    for f in files:
        if isinstance(f, list):
            total += folder_size(f)  # Recursive call for subfolder
        else:
            total += f  # File size
    return total

print(folder_size([10, [20, 30], 40]))

Calculates total size of files and subfolders recursively by checking if element is a list (subfolder) or a file size.

Output:

100