Anthony Bañon Arias

Posted on May 8 • Edited on Jun 8

What is Recursion?

#recursion

Guide for Beginners

Recursion is a powerful programming concept where a function calls itself to solve smaller instances of a problem. This technique is especially useful when a problem can be naturally divided into similar subproblems.

✅ When Can Recursion Be Used?

To use recursion effectively, three key conditions must be met:

Base Case: A condition that stops the recursion.
Recursive Case: The function must call itself with a simpler or smaller input.
Progress Toward Base Case: Each recursive call must move closer to the base case.

If these aren't met, the function will recurse infinitely, eventually causing a stack overflow.

📂 Types of Recursion

Type	Description	Example	Where It Resolves
Simple Recursion	Function calls itself once per invocation	Factorial, Fibonacci	When returning from base
Tail Recursion	Recursive call is the last statement, no operation after it	Accumulative sum	During descent (no waiting)
Mutual Recursion	Functions call each other	`is_even()` ↔ `is_odd()`	When returning from base
Multiple Recursion	Function makes multiple recursive calls	Fibonacci, Tree Traversal	When returning from base
Backtracking	Explore options and undo decisions when needed	Sudoku solver, Maze	When returning (and exploring again)
Descending Recursion	Goes down to the base case and then computes on the way back	Factorial, Fibonacci	After reaching the base case
Accumulative Recursion	Builds up a result during the recursive descent	Summing a list, Tree folding	During descent

🧩 Key Recursion Patterns

Pattern	Description	Example
📉 Descending	Reaches the base case and solves on the way back	Factorial, Towers of Hanoi
📈 Accumulative	Builds a result while descending	Sum list elements
🔁 Mutual (Alternating)	Alternates between functions	`is_even(n)`, `is_odd(n)`
🔄 Backtracking	Explores paths, undoes, and tries again	Maze solver, n-Queens

✍️ Simple Examples

1. Factorial (Simple Recursion)

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

2. Tail Recursion (Sum Accumulator)

def sum_tail(n, acc=0):
    if n == 0:
        return acc
    return sum_tail(n - 1, acc + n)

3. Mutual Recursion (Even/Odd)

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

4. Multiple Recursion (Fibonacci)

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

5. Backtracking (Maze Path Finder - conceptually)

def solve_maze(maze, x, y):
    if is_goal(x, y):
        return True
    for direction in possible_moves(x, y):
        if solve_maze(maze, new_x, new_y):
            return True
    return False  # backtrack if no direction works

📋 Summary Table

Type	Simple	Multiple	Accumulative	Descending	Backtracking	Resolves When
Factorial	✅	❌	❌	✅	❌	After base case
Fibonacci	✅	✅	❌	✅	❌	After base case
Sum Accumulated	✅	❌	✅	❌	❌	During descent
is_even/is_odd	❌	❌	❌	✅	❌	After base case
Maze Solver	❌	✅	❌	✅	✅	During backtrack

🧠 Conclusion

Recursion is more than just a function calling itself — it's a way of thinking about problems. It allows you to divide tasks into smaller parts, handle dynamic structures like trees and graphs, and model decision-making processes like backtracking. By understanding the types, patterns, and proper use cases, you can write more elegant and efficient code.

Want to dive deeper? Try visualizing recursion using stack traces or call trees — it really helps!

✍️ Written by Anthony Banion – passionate backend developer, tech writer & student of systems analysis. Follow me for more learning guides!

DEV Community