Recursion Basics

Introduction

Recursion is a programming technique where a function calls itself to solve a problem. It is commonly used in computer science to break large problems into smaller and simpler subproblems.

Recursion is widely used in algorithms, mathematics, searching, sorting, tree structures, and problem-solving applications.

Objectives

By the end of this training, you will be able to:

• Understand the concept of recursion
• Identify base cases and recursive cases
• Write simple recursive functions
• Solve mathematical and logical problems using recursion
• Compare recursion with loops
• Understand advantages and limitations of recursion

What is Recursion

Recursion occurs when a function repeatedly calls itself until a specific condition is met.

A recursive function usually contains:

• Base Case
• Recursive Case

The base case stops the function from calling itself endlessly, while the recursive case continues the process.

Structure of a Recursive Function

Basic structure:

def function_name():
    if condition:
        return value
    else:
        return function_name()

Understanding the Base Case

The base case is the stopping condition in recursion. Without a base case, the function would continue forever and cause an error.

Example:

def countdown(n):
    if n == 0:
        print("Finished")
    else:
        print(n)
        countdown(n - 1)

How Recursion Works

When a recursive function is called:

1. The function executes
2. It calls itself with a smaller problem
3. Each call waits for the next call to finish
4. The process continues until the base case is reached
5. The function calls return one by one

Example of Recursion

Factorial Calculation

Factorial of 5:

5 × 4 × 3 × 2 × 1 = 120

Recursive solution:

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

print(factorial(5))

Output:

120

Recursive Countdown Example

def countdown(number):
    if number == 0:
        print("Done")
    else:
        print(number)
        countdown(number - 1)

countdown(5)

Recursive Sum Example

def recursive_sum(n):
    if n == 1:
        return 1
    return n + recursive_sum(n - 1)

print(recursive_sum(5))

Output:

15

Recursion vs Loops

Recursion

• Function calls itself
• Easier for complex problems
• Uses more memory
• Cleaner code for some algorithms

Loops

• Repeats using iteration
• Faster for simple repetition
• Uses less memory
• Easier for beginners

Advantages of Recursion

• Simplifies complex problems
• Produces cleaner and shorter code
• Useful for tree and graph structures
• Common in divide-and-conquer algorithms
• Helps solve mathematical problems naturally

Disadvantages of Recursion

• Can use more memory
• Slower than loops in some cases
• Risk of infinite recursion
• Difficult to debug for beginners

Common Applications of Recursion

Recursion is commonly used in:

• Factorial calculations
• Fibonacci sequence
• Tree traversal
• Searching algorithms
• Sorting algorithms
• File directory navigation
• Mathematical computations

Fibonacci Sequence Example

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

print(fibonacci(6))

Output:

8

Best Practices for Recursion

• Always define a clear base case
• Reduce the problem size in each call
• Avoid unnecessary recursive calls
• Test with small inputs first
• Use recursion only when it improves clarity

Real World Uses of Recursion

• Website menu systems
• Folder and file navigation
• Artificial intelligence algorithms
• Game development
• Data structure processing
• Search engines

Conclusion

Recursion is a powerful programming technique used to solve problems by breaking them into smaller tasks. Understanding recursion improves problem-solving skills and helps developers work with advanced algorithms and data structures efficiently.