The Concept

Recursion might seem like a puzzle at first, but it’s like opening a set of Russian nesting dolls. Each doll contains a smaller one, just as a recursive function calls a smaller version of itself until it reaches a point where it doesn’t need to call anymore.

Imagine you want to calculate the factorial of a number. Factorial of a number is the product of all positive integers less than or equal to that number. Using recursion, it looks like this:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

In simpler terms, the function multiplies the number by the factorial of a smaller number, and it keeps going until it reaches zero. This is like opening each nesting doll until you find the smallest one, and then you know the answer.

Recursion, in a nutshell, is like solving a big problem by breaking it into smaller, similar problems. It’s a way of thinking that leads to elegant solutions in programming and other areas.

Base Case vs. Recursive Case

• Base Case: It’s the stopping point of recursion. Without it, recursion would go on forever.
  • Example: In a factorial function, the base case is when the input is 0, and the function returns 1.
• Recursive Case: It’s when the function calls itself with modified arguments to move towards the base case.
  • Example: In the factorial function, if the input is greater than 0, the function calls itself with (n-1) until it reaches the base case.

Visualising Recursion: Tree Diagrams and Call Stacks

• Tree Diagrams: They show function calls as branches of a tree.
  • Example: Drawing a tree for factorial(5) would show factorial(5) calling factorial(4), then factorial(4) calling factorial(3), and so on.
• Call Stacks: They track function calls and their local variables.
  • Example: When factorial(5) calls factorial(4), factorial(5) is added to the stack. As each function returns, it’s removed from the stack.

Factorial Function

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Example usage

result = factorial(5)
print(result)  # Output: 120

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Example usage

result = fibonacci(6)
print(result)  # Output: 8

Towers of Hanoi

The Towers of Hanoi is a puzzle where you have three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a stack in ascending order of size on one rod, with the smallest disk on top.

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print("Move disk 1 from", source, "to", target)
        return
    hanoi(n-1, source, auxiliary, target)
    print("Move disk", n, "from", source, "to", target)
    hanoi(n-1, auxiliary, target, source)

Example usage

hanoi(3, 'A', 'C', 'B')

Binary Search

Binary search is a search algorithm that finds the position of a target value within a sorted array.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Example usage

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search(arr, target)
print("Element found at index:", result)  # Output: 6

File System Traversal

Imagine you have a computer program that needs to look through all the folders and files on your computer. Recursion helps the program by letting it go into each folder, look at what’s inside, and then go into any folders it finds there, repeating this process until it’s looked through everything.

Maze Solving

Think of a maze where you need to find your way out. Recursion is like taking steps and making decisions at each turn. If you hit a dead-end, you go back and try another path until you find the way out.

Parsing Expressions

When a computer needs to understand and solve math problems written in a certain way, like “(3 + 4) * 5”, recursion helps by breaking down the problem into smaller parts and solving them step by step.

Advantages

Elegance: Recursion offers a beautiful solution for problems with repetitive structures, like trees or mathematical sequences.

Clarity: It helps write clearer, more concise code by mirroring the problem’s description, making it easier to understand and maintain.

Challenges

Performance: Recursion can lead to performance issues, especially with deeply nested functions, potentially causing stack overflow errors.

Complexity for Beginners: Understanding recursion can be tough for beginners due to its abstract nature and the need to grasp concepts like base cases and recursive cases.

Knowing When to Use Recursion

Identifying Suitable Problems: Recursion works well for problems that can be broken down into smaller, similar subproblems, like tree traversal or backtracking.

Considering Alternatives: Sometimes, using loops (iteration) might be better if the problem doesn’t naturally fit recursion or if efficiency is a concern.

Optimisation Techniques

Tail Recursion Optimisation: For recursive functions where the last operation is the recursive call, some languages can optimise this to prevent stack overflow.

Memoisation for Efficiency: To speed up recursive algorithms, store results of previous calculations. When the same inputs occur again, return the cached result instead of recalculating it.