RECURSION

Complete Study Notes for First■Year Students

"A function that calls itself — elegantly."

■ Subject Data Structures & Algorithms

■ Level Beginner → Advanced

■ Language Python (pseudocode style)

■ Topics Base Cases · Types · Examples · Complexity

A function that solves a problem by calling itself on a smaller version

■ Self-Reference of the same problem.

The stopping condition — without it, recursion runs forever (stack

■ Base Case overflow!).

The part where the function calls itself, making progress toward the
■■ Recursive Case base case.
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter

Table of Contents
Ch. 1 What is Recursion? Understanding the concept

Ch. 2 Anatomy of a Recursive Function Base case & Recursive case

Ch. 3 How Recursion Works Internally The Call Stack

Ch. 4 Types of Recursion 6 different types explained

Ch. 5 Basic Examples Factorial, Fibonacci, Power

Ch. 6 Intermediate Examples Arrays, Strings, Palindrome

Merge Sort, Tower of Hanoi,

Ch. 7 Advanced Examples Backtracking

Ch. 8 Recursion vs Iteration When to use which

Ch. 9 Common Mistakes & Tips Pitfalls to avoid

Ch. 10 Time & Space Complexity Analyzing recursive programs

Page 2 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 1

What is Recursion?
Understanding the concept from scratch

Definition
Recursion is a programming technique where a function calls itself to solve a problem by breaking it
into smaller, simpler sub-problems of the same type. Each call works on a reduced version of the
original problem until a simple, directly solvable case is reached — called the base case.

A Real-World Analogy
■ Mirror in a Mirror

Hold two mirrors facing each other. You see an infinite tunnel of reflections — each reflection
contains a smaller version of itself. That's recursion in nature.

■ Folders in Folders

A folder on your computer can contain other folders, which contain more folders. To find a file,
you open each folder, and if it has sub-folders, you repeat the same process inside them. This is
exactly recursive thinking.

■ Matryoshka Dolls

Russian nesting dolls — each doll contains a smaller doll. To count all dolls, you open one,
count it, then solve the same problem for the remaining dolls inside.

Formal Definition
A function f is called recursive if it is defined in terms of itself:

f(n) = base_case if n is simple enough

f(n) = combine(f(smaller)) otherwise

Example: f(n) = n * f(n-1) [Factorial]

f(0) = 1 [Base Case]

Page 3 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Why Learn Recursion?

• Many real-world problems are naturally recursive (trees, graphs, divide & conquer algorithms).
• Recursion leads to elegant, shorter code compared to iterative solutions.
• Essential for understanding sorting algorithms (Merge Sort, Quick Sort).
• Required for solving problems on binary trees, linked lists, and backtracking.
• Appears in almost every technical interview at top companies.

Page 4 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 2

Anatomy of a Recursive Function

Base Case & Recursive Case

The Two Essential Parts

Every correct recursive function MUST have these two parts:

Part What it does What happens without it

■ Base Case Stops the recursion when the simplest Without it → INFINITE RECURSION → Stack Overflo
case is reached

■ Recursive Case Calls the function again on a smaller/simpler

Without it → No recursion happens, just a regular fun
input

Template / Blueprint
def recursive_function(input):

# ■■ BASE CASE ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

if input is simplest possible:

return answer_directly # NO recursive call here

# ■■ RECURSIVE CASE ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

smaller_input = make_input_smaller(input)

result = recursive_function(smaller_input)

return combine(result, input)

Steps to Write Any Recursive Function

Step 1 — Identify the Base Case

Ask: 'What is the simplest input for which I know the answer directly?' For factorial, n=0 gives 1.
For sum of list, empty list gives 0.

Step 2 — Identify the Recursive Case

Page 5 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Ask: 'How can I express the solution for n in terms of a solution for n-1 (or smaller)?' factorial(n)
= n × factorial(n-1).

Step 3 — Trust the recursion

Assume your function works correctly for smaller inputs. You just need to use that result
correctly. This is called the 'Leap of Faith'.

Step 4 — Verify base and recursive cases connect

Make sure each recursive call brings you closer to the base case. Otherwise you'll get infinite
recursion.

Page 6 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 3

How Recursion Works Internally

Understanding the Call Stack

What is the Call Stack?

When a function is called, Python (and most languages) create a stack frame — a block of memory
that stores the function's local variables and the point to return to when the function finishes. The call
stack is the pile of all active stack frames, growing with each call and shrinking as calls return.

Visualizing factorial(4)
Let's trace factorial(4) step by step:

def factorial(n):

if n == 0: # base case

return 1

return n * factorial(n - 1) # recursive case

Call Stack — Going DOWN (building up):

Frame Call Waiting for...

4 (bottom) factorial(4) factorial(3) to return

3 factorial(3) factorial(2) to return

2 factorial(2) factorial(1) to return

1 factorial(1) factorial(0) to return

0 (top) factorial(0) returns 1 immediately ■

Call Stack — Going UP (unwinding):

Frame Returns Computation

0 1 base case → 1

1 1 1×1=1

2 2 2×1=2

Page 7 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Frame Returns Computation

3 6 3×2=6

4 24 4 × 6 = 24 ← Final Answer!

■■ Stack Overflow

If there is no base case (or it's never reached), the call stack keeps growing until memory runs
out. Python will raise: RecursionError: maximum recursion depth exceeded.

Python's default recursion limit is 1000 calls. You can check it with: import sys;
[Link]()

Page 8 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 4

Types of Recursion
6 Different Types with Examples

1. Direct Recursion
A function calls itself directly.

def countdown(n):

if n == 0: return

print(n)

countdown(n - 1) # direct call to itself

2. Indirect Recursion
Function A calls Function B, which calls Function A. They call each other in a cycle.

def is_even(n):

if n == 0: return True

return is_odd(n - 1) # calls is_odd

def is_odd(n):

if n == 0: return False

return is_even(n - 1) # calls is_even

3. Tail Recursion
The recursive call is the LAST operation in the function — nothing is done after it returns. Many
compilers optimize this into a loop (tail-call optimization).

def factorial_tail(n, accumulator=1):

if n == 0:

return accumulator # base case

return factorial_tail(n-1, n * accumulator) # LAST operation

Page 9 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

4. Head Recursion
The recursive call happens FIRST, before any other processing in the function.

def print_reverse(n):

if n == 0: return

print_reverse(n - 1) # FIRST — recurse

print(n) # THEN — process (prints in order 1..n)

5. Tree Recursion
A function makes MORE THAN ONE recursive call. The calls branch out like a tree.

def fibonacci(n):

if n <= 1:

return n

return fibonacci(n-1) + fibonacci(n-2) # TWO recursive calls

6. Nested Recursion
The argument to the recursive call is itself a recursive call. Rare but interesting.

def ackermann(m, n):

if m == 0: return n + 1

if n == 0: return ackermann(m-1, 1)

return ackermann(m-1, ackermann(m, n-1)) # nested!

Page 10 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 5

Basic Examples
Start simple — build your intuition!

Example 1 — Factorial (n!)

Problem: Compute n! = n × (n-1) × (n-2) × ... × 1. By definition, 0! = 1.

Mathematical recurrence:
• factorial(0) = 1 [Base Case]
• factorial(n) = n × factorial(n-1) [Recursive Case]

def factorial(n):

# Base Case: 0! = 1

if n == 0:

return 1

# Recursive Case: n! = n × (n-1)!

return n * factorial(n - 1)

# Test

print(factorial(5)) # Output: 120

print(factorial(0)) # Output: 1

Call n Returns

factorial(5) 5 5 × factorial(4) = 5 × 24 = 120

factorial(4) 4 4 × factorial(3) = 4 × 6 = 24

factorial(3) 3 3 × factorial(2) = 3 × 2 = 6

factorial(2) 2 2 × factorial(1) = 2 × 1 = 2

factorial(1) 1 1 × factorial(0) = 1 × 1 = 1

factorial(0) 0 1 (Base Case!)

Example 2 — Sum of First N Numbers

Problem: Find 1 + 2 + 3 + ... + n.

Page 11 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

def sum_n(n):

if n == 0: # Base: sum of 0 numbers = 0

return 0

return n + sum_n(n - 1) # Recursive: add n to sum of rest

print(sum_n(5)) # 5+4+3+2+1+0 = 15

Example 3 — Power (x raised to n)

Problem: Compute xn without using ** operator.

def power(x, n):

if n == 0: # x^0 = 1 always

return 1

return x * power(x, n - 1) # x^n = x * x^(n-1)

print(power(2, 10)) # Output: 1024

print(power(3, 4)) # Output: 81

■ Optimized Power — Fast Exponentiation

We can make power even faster! Instead of n calls, use n/2 calls:

If n is even: x^n = (x^(n/2))^2

If n is odd: x^n = x × x^(n-1) → This runs in O(log n) time!

def fast_power(x, n):

if n == 0: return 1

half = fast_power(x, n // 2)

if n % 2 == 0:

return half * half # Even

else:

return x * half * half # Odd

Example 4 — Print N to 1 and 1 to N

This shows the difference between head recursion and tail recursion beautifully.

Page 12 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

# Print N down to 1 (process BEFORE recursing = tail recursion)

def print_n_to_1(n):

if n == 0: return

print(n) # Print first

print_n_to_1(n-1) # Then recurse

# Print 1 up to N (recurse BEFORE processing = head recursion)

def print_1_to_n(n):

if n == 0: return

print_1_to_n(n-1) # Recurse first

print(n) # Then print (on the way back UP)

Page 13 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 6

Intermediate Examples
Arrays, Strings & More

Example 5 — Fibonacci Sequence

Problem: Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13 ... where fib(n) = fib(n-1) + fib(n-2).

Base cases: fib(0) = 0, fib(1) = 1

def fibonacci(n):

if n == 0: return 0 # Base case 1

if n == 1: return 1 # Base case 2

return fibonacci(n-1) + fibonacci(n-2) # Tree recursion!

for i in range(8):

print(fibonacci(i), end=' ') # 0 1 1 2 3 5 8 13

■■ Fibonacci is Slow! (Exponential Time)

fibonacci(5) calls fibonacci(3) and fibonacci(4).

fibonacci(4) ALSO calls fibonacci(3) — same work done twice!

This leads to O(2^n) time — extremely slow for large n.

Solution: Use Memoization (store results to avoid recomputation).

# Fibonacci with Memoization (much faster!)

memo = {}

def fib_memo(n):

if n <= 1: return n

if n in memo: # Already computed? Return stored value

return memo[n]

memo[n] = fib_memo(n-1) + fib_memo(n-2) # Store result

return memo[n]

Page 14 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

print(fib_memo(50)) # Runs instantly! Without memo: takes forever

Example 6 — Sum of an Array

Problem: Find the sum of all elements in a list using recursion (no loops!).

def array_sum(arr):

# Base case: empty array has sum 0

if len(arr) == 0:

return 0

# Recursive: first element + sum of rest

return arr[0] + array_sum(arr[1:])

print(array_sum([1, 2, 3, 4, 5])) # Output: 15

print(array_sum([])) # Output: 0

Call arr Returns

array_sum([1,2,3,4,5]) [1,2,3,4,5] 1 + 14 = 15

array_sum([2,3,4,5]) [2,3,4,5] 2 + 12 = 14

array_sum([3,4,5]) [3,4,5] 3 + 9 = 12

array_sum([4,5]) [4,5] 4+5=9

array_sum([5]) [5] 5+0=5

array_sum([]) [] 0 ← Base Case

Example 7 — Check Palindrome

Problem: A palindrome reads the same forwards and backwards. Check if a string is a palindrome.

Idea: If first and last characters match, check if the middle portion is also a palindrome.

def is_palindrome(s):

# Base cases: empty string or single char = palindrome

if len(s) <= 1:

return True

# If first and last don't match → NOT palindrome

if s[0] != s[-1]:

return False

Page 15 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

# Recurse on the middle portion

return is_palindrome(s[1:-1])

print(is_palindrome("racecar")) # True

print(is_palindrome("hello")) # False

print(is_palindrome("madam")) # True

print(is_palindrome("a")) # True

Example 8 — Reverse a String

def reverse_string(s):

if len(s) == 0: # Base: empty string

return ''

# Last character + reverse of the rest

return s[-1] + reverse_string(s[:-1])

print(reverse_string("hello")) # "olleh"

print(reverse_string("Python")) # "nohtyP"

Example 9 — Count Occurrences in Array

def count_occurrences(arr, target):

if len(arr) == 0: # Base: empty array has 0 occurrences

return 0

# Check first element, add to count of rest

count = 1 if arr[0] == target else 0

return count + count_occurrences(arr[1:], target)

print(count_occurrences([1,2,3,2,4,2], 2)) # Output: 3

Page 16 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 7

Advanced Examples
Tower of Hanoi · Merge Sort · Backtracking

Example 10 — Tower of Hanoi

Problem: Move n disks from peg A to peg C using peg B as helper. Rules: (1) Move one disk at a time.
(2) Never place a larger disk on a smaller one.

■ The Classic Recursion Problem

Tower of Hanoi is THE example that demonstrates recursive thinking perfectly.

The recursive insight: to move n disks from A to C, first move (n-1) disks from A to B, then move
the big disk from A to C, then move (n-1) disks from B to C.

This leads to 2^n - 1 total moves — provably optimal!

def hanoi(n, source, target, helper):

# Base Case: only 1 disk — move it directly

if n == 1:

print(f'Move disk 1 from {source} to {target}')

return

# Step 1: Move top (n-1) disks from source to helper

hanoi(n-1, source, helper, target)

# Step 2: Move the big disk from source to target

print(f'Move disk {n} from {source} to {target}')

# Step 3: Move (n-1) disks from helper to target

hanoi(n-1, helper, target, source)

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

Output for hanoi(3, 'A', 'C', 'B'):

Page 17 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Step Action

1 Move disk 1 from A to C

2 Move disk 2 from A to B

3 Move disk 1 from C to B

4 Move disk 3 from A to C

5 Move disk 1 from B to A

6 Move disk 2 from B to C

7 Move disk 1 from A to C ■ Done! (2^3 - 1 = 7 moves)

Example 11 — Merge Sort

Problem: Sort an array efficiently. Merge Sort uses divide-and-conquer recursion.

Idea: Divide the array in half, sort each half recursively, then merge the two sorted halves.

def merge_sort(arr):

# Base Case: array of 0 or 1 element is already sorted

if len(arr) <= 1:

return arr

# Divide: split into two halves

mid = len(arr) // 2

left = merge_sort(arr[:mid]) # Sort left half

right = merge_sort(arr[mid:]) # Sort right half

# Conquer: merge the two sorted halves

return merge(left, right)

def merge(left, right):

result = []

i = j = 0

while i < len(left) and j < len(right):

if left[i] <= right[j]:

[Link](left[i]); i += 1

else:

[Link](right[j]); j += 1

Page 18 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

[Link](left[i:]) # Remaining elements

[Link](right[j:])

return result

arr = [38, 27, 43, 3, 9, 82, 10]

print(merge_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]

Example 12 — Binary Search (Recursive)

Problem: Find a target in a sorted array. Binary search is naturally recursive.

def binary_search(arr, target, low, high):

# Base Case: search space is empty

if low > high:

return -1 # Not found

mid = (low + high) // 2

if arr[mid] == target:

return mid # Found!

elif arr[mid] < target:

return binary_search(arr, target, mid+1, high) # Search right

else:

return binary_search(arr, target, low, mid-1) # Search left

arr = [1, 3, 5, 7, 9, 11, 13, 15]

print(binary_search(arr, 7, 0, len(arr)-1)) # Output: 3 (index)

print(binary_search(arr, 6, 0, len(arr)-1)) # Output: -1 (not found)

Example 13 — Backtracking: Generate All Subsets

Problem: Generate all possible subsets (power set) of a given set. Backtracking is a pattern where we
explore all possibilities and undo choices that don't work.

def generate_subsets(nums, index=0, current=[]):

# Print current subset

print(current[:])

# Try including each remaining element

Page 19 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

for i in range(index, len(nums)):

[Link](nums[i]) # Choose

generate_subsets(nums, i+1, current) # Explore

[Link]() # Un-choose (backtrack)

generate_subsets([1, 2, 3])

# Output: [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3]

■ Backtracking Pattern

Choose: Pick an option (add to current solution).

Explore: Recurse to explore with that choice.

Un-choose: Remove the choice (backtrack) to try other options.

This pattern is used in: N-Queens, Sudoku solver, maze solving, permutations.

Page 20 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 8

Recursion vs Iteration
When to use which?

Aspect Recursion Iteration

Code style Shorter, elegant, mirrors math More explicit, verbose

Memory Uses call stack (extra memory) Usually constant memory

Speed Overhead from function calls Generally faster

Debugging Harder to trace Easier to trace

Best for Trees, graphs, divide & conquer Simple loops, counters

Risk Stack Overflow if no base case Infinite loop

Readability High for recursive problems High for sequential problems

Side-by-side comparison — Factorial

# Iterative

def factorial_iter(n):

result = 1

for i in range(1, n+1):

result *= i

return result

# Recursive

def factorial_rec(n):

if n == 0:

return 1

return n * factorial_rec(n-1)

Page 21 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 9

Common Mistakes & Tips

Avoid these pitfalls!

■ Mistake 1: Missing Base Case

This causes infinite recursion and crashes.

def bad_factorial(n):

return n * bad_factorial(n-1) # No base case! Infinite loop

■ Mistake 2: Wrong Base Case

The base case doesn't cover all stopping conditions.

def sum_n(n): # WRONG — what if n is negative?

if n == 0: return 0 # This is never reached for negative n

return n + sum_n(n-1)

def sum_n_fixed(n): # CORRECT

if n <= 0: return 0 # Handles 0 and negative

■ Mistake 3: Not Making Progress

The recursive call doesn't reduce the problem — it loops forever.

def bad(n):

if n == 0: return

bad(n) # Oops! n never changes → infinite

■ Tip 1: Trust the Recursion

When writing recursion, assume your function WORKS for smaller inputs. Focus only on the
current step.

■ Tip 2: Draw the recursion tree

Page 22 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

For tree recursion, draw out the calls on paper. It helps you see overlapping sub-problems.

■ Tip 3: Always trace through a small example

Before coding, manually trace: factorial(3) → 3×factorial(2) → 3×2×factorial(1) → ...

Page 23 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

Chapter 10

Time & Space Complexity

Analyzing recursive programs

For recursive programs, we use Recurrence Relations to find time complexity. Space complexity is
determined by the maximum depth of the call stack.

Algorithm Recurrence Time Space (Stack)

Factorial T(n) = T(n-1) + O(1) O(n) O(n)

Fibonacci (naive) T(n) = T(n-1) + T(n-2) O(2^n) O(n)

Fibonacci (memo) T(n) = O(n) total O(n) O(n)

Binary Search T(n) = T(n/2) + O(1) O(log n) O(log n)

Merge Sort T(n) = 2T(n/2) + O(n) O(n log n) O(n)

Power (basic) T(n) = T(n-1) + O(1) O(n) O(n)

Power (fast) T(n) = T(n/2) + O(1) O(log n) O(log n)

Tower of Hanoi T(n) = 2T(n-1) + O(1) O(2^n) O(n)

■ Master Theorem (Quick Reference)

For recurrences of the form T(n) = aT(n/b) + f(n):

• If f(n) < n^(log_b a) → T(n) = O(n^log_b_a)

• If f(n) = n^(log_b a) → T(n) = O(n^log_b_a × log n)

• If f(n) > n^(log_b a) → T(n) = O(f(n))

Example: Merge Sort: a=2, b=2, f(n)=n → f(n) = n^(log_2 2) = n → Case 2 → O(n log n)

Summary — What We Covered

Topic Key Takeaway

Page 24 of 25
RECURSION — Complete Study Notes CS Fundamentals | First Year

What is Recursion? Function that calls itself on smaller input

Base Case Stopping condition — MUST exist

Recursive Case Call with smaller input, make progress

Call Stack Each call adds a frame; unwinds when returning

Types Direct, Indirect, Tail, Head, Tree, Nested

Basic Examples Factorial, Sum, Power, Print sequences

Intermediate Fibonacci+Memo, Array Sum, Palindrome, Reverse

Advanced Tower of Hanoi, Merge Sort, Binary Search, Backtracking

vs Iteration Recursion = elegant; Iteration = efficient

Complexity Use recurrence relations; watch for stack depth

"To understand recursion, you must first understand recursion."

Page 25 of 25