ICS 2105 – DATA STRUCTURES AND ALGORITHMS

Topic: Recursion

DATA STRUCTURES AND ALGORITHMS

TOPIC: RECURSION

1. Topic Purpose:

The topic "Recursion" in Data Structures and Algorithms is aimed at helping undergraduate
Information Technology students understand how certain problems can be solved more
efficiently using recursive techniques. Recursion provides a different way of thinking about
problem-solving by allowing a function to call itself in order to break down a complex problem
into smaller, more manageable parts. This concept is foundational for understanding many
advanced topics such as backtracking, divide and conquer algorithms, and dynamic
programming. By the end of this topic, students should be able to confidently apply recursion to
solve programming problems and understand how it works behind the scenes in memory.

2. Learning Objectives:

• Understand the concept of recursion and its fundamental structure.

• Identify and write base and recursive cases in recursive functions.
• Apply recursion to solve standard algorithmic problems such as factorial and Fibonacci.
• Analyze how recursion works with the call stack and memory.

3. Detailed Notes:

3.1 Introduction to Recursion

Recursion is a programming technique where a function calls itself to solve smaller instances of
the same problem. In simple terms, recursion allows a problem to be defined in terms of itself. It
breaks down a problem into smaller sub-problems and then solves each of those recursively. This
approach is particularly useful when the problem can be naturally divided into similar sub-
problems.

Imagine you are looking at a mirror that reflects another mirror. What you see is a repeated
image going into the distance. Recursion works similarly, where a function keeps calling itself
until a certain condition is met.

3.2 How Recursion Works

A recursive function usually has two main parts:

1. Base Case: This is the condition that stops the recursion. Without a base case, the
function would call itself forever, leading to a stack overflow error.

Dr. Lango 1
ICS 2105 – DATA STRUCTURES AND ALGORITHMS

2. Recursive Case: This is the part of the function where the function calls itself.

Example: Let’s consider a basic example — finding the factorial of a number.

Factorial of a number n (written as n!) is defined as:

• n! = n * (n-1) * (n-2) * ... * 1

• With recursion: n! = n * (n-1)!
• And 1! = 1 (this is our base case)

Here’s how we can write a recursive function in Python:

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

3.3 Tracing Recursive Function Calls

When we call factorial(3), the following happens:

• factorial(3) returns 3 * factorial(2)

• factorial(2) returns 2 * factorial(1)
• factorial(1) returns 1 (base case)

Now we go back up the call stack:

• factorial(2) = 2 * 1 = 2
• factorial(3) = 3 * 2 = 6

So, factorial(3) returns 6.

3.4 The Call Stack

When a function is called, the computer stores information about that call in a special memory
structure called the call stack. Every recursive call adds a new frame to the call stack. When a
base case is reached, the calls start resolving from the most recent one back to the first.

This is why recursion can be memory-intensive if the depth of recursion is large. If there are too
many recursive calls without reaching the base case, the stack may overflow.

3.5 Examples of Recursion

1. Fibonacci Series:

Dr. Lango 2
ICS 2105 – DATA STRUCTURES AND ALGORITHMS

The Fibonacci sequence is a series of numbers where each number is the sum of the two
preceding ones. It starts like this: 0, 1, 1, 2, 3, 5, 8, ...

Recursive implementation:

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

Note: This version is inefficient for large n due to repeated calculations.

2. Sum of n Natural Numbers:

def sum_n(n):
if n == 1:
return 1
else:
return n + sum_n(n - 1)

3. Reverse a String Using Recursion:

def reverse_string(s):
if len(s) == 0:
return s
else:
return reverse_string(s[1:]) + s[0]

3.6 Recursion vs Iteration

Both recursion and iteration can be used to solve the same problems, but they differ in approach.

• Recursion is cleaner and more intuitive for problems that have a natural recursive
structure (like tree traversal).
• Iteration is generally more efficient in terms of memory.

Example (Factorial using iteration):

def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result

3.7 When to Use Recursion

Recursion is ideal when:

Dr. Lango 3
ICS 2105 – DATA STRUCTURES AND ALGORITHMS

• The problem can be broken down into smaller sub-problems of the same type.
• The number of sub-problems is not large enough to cause memory issues.
• The recursive approach makes the code cleaner and easier to understand.

Common examples include:

• Tree traversal
• Graph traversal
• Solving puzzles like Tower of Hanoi
• Backtracking problems (e.g., Sudoku)
• Divide and conquer algorithms (e.g., Merge Sort, Quick Sort)

3.8 Tail Recursion

Tail recursion is a special form of recursion where the recursive call is the last operation in the
function.

Example:

def tail_factorial(n, acc=1):

if n == 0:
return acc
else:
return tail_factorial(n - 1, acc * n)

Some programming languages optimize tail recursion to prevent stack overflow. However,
Python does not perform tail recursion optimization.

3.9 Advantages of Recursion

• Simpler code for problems that have recursive structures.

• Easier to write and understand for complex problems.
• Useful for problems involving divide and conquer strategies.

3.10 Disadvantages of Recursion

• Can lead to performance issues due to overhead from multiple function calls.
• Uses more memory because each function call is stored on the call stack.
• Risk of stack overflow if the base case is not properly defined or recursion is too deep.

3.11 Converting Recursive to Iterative

Sometimes, you may need to convert a recursive function to an iterative one for better
performance. This involves using loops and stacks to mimic the call stack.

Example: Converting recursive factorial to iterative was shown earlier.

Dr. Lango 4
ICS 2105 – DATA STRUCTURES AND ALGORITHMS

3.12 Summary

Recursion is a powerful tool in programming that helps solve problems by breaking them down
into smaller parts. It involves a function calling itself and relies on a base case to stop the
recursion. While recursion is elegant and closely matches mathematical definitions, it must be
used carefully to avoid memory issues. Through practice with standard problems like factorial,
Fibonacci, and tree traversals, students can become proficient in applying recursion effectively in
their programming tasks.

Understanding recursion lays the foundation for tackling more complex algorithmic problems
and mastering advanced topics in data structures and algorithms.

Dr. Lango 5