Recursion

Introduction to Recursion

Imagine you have a set of Russian nesting dolls, where each doll contains a smaller doll inside it, and that smaller doll contains an even smaller one, and so on. To open the largest doll and see the smallest one, you first open the largest, then the next smaller, continuing until you reach the tiniest doll that cannot be opened further. This process of repeating the same action on a smaller scale is similar to the idea of recursion in programming.

Recursion is a method where a function solves a problem by calling itself to solve smaller instances of the same problem. Instead of using loops or repeated code, recursion breaks down complex problems into simpler, manageable parts.

Why use recursion? Some problems are naturally hierarchical or self-similar, such as calculating factorials, navigating file directories, or solving puzzles like the Tower of Hanoi. Recursion provides a clean and elegant way to express solutions to such problems.

Recursion differs from iteration (loops) in that it uses function calls and the program's call stack to keep track of progress, rather than explicit looping constructs. While loops repeat actions explicitly, recursion repeats by self-calling functions.

Before diving into code, let's build an intuitive understanding of recursion through simple examples and analogies.

Definition and Structure of Recursive Functions

Every recursive function has two essential parts:

Base Case: This is the simplest instance of the problem, which can be solved directly without further recursion. It acts as the stopping condition to prevent infinite recursion.
Recursive Case: This part breaks the problem into smaller subproblems and calls the same function to solve these smaller parts.

Think of the base case as the smallest doll that cannot be opened, and the recursive case as the action of opening a doll to find a smaller one inside.

The general form of a recursive function looks like this:

graph TD    Start[Start Function]    CheckBase{Is problem simple enough?}    BaseCase[Return direct answer]    RecursiveCase[Call function on smaller problem]    Combine[Combine result if needed]    End[Return result]    Start --> CheckBase    CheckBase -- Yes --> BaseCase --> End    CheckBase -- No --> RecursiveCase --> Combine --> End

In this flowchart, the function first checks if it has reached the base case. If yes, it returns the answer immediately. If not, it calls itself with a smaller problem and then combines the result to form the final answer.

Types of Recursion

Type of Recursion	Definition	Example
Direct Recursion	A function calls itself directly.	function factorial(n): if n == 0: return 1 else: return n * factorial(n-1)
Indirect Recursion	Function A calls Function B, and Function B calls Function A.	function A(): // some code B()function B(): // some code A()
Tail Recursion	The recursive call is the last operation in the function, allowing some compilers to optimize and reuse stack frames.	function tailFactorial(n, acc=1): if n == 0: return acc else: return tailFactorial(n-1, n*acc)

Why is tail recursion important? Because it can be optimized by some compilers or interpreters to avoid increasing the call stack depth, preventing stack overflow and improving performance.

Worked Example 1: Calculating Factorial Using Recursion Easy

Example 1: Calculating Factorial Using Recursion Easy

Find the factorial of 3 using a recursive function. Recall that factorial of a number \( n \) (denoted \( n! \)) is the product of all positive integers up to \( n \).

Step 1: Define the base case. For factorial, \( 0! = 1 \).

Step 2: Define the recursive case: \( n! = n \times (n-1)! \) for \( n > 0 \).

Step 3: Write the recursive function in pseudocode:

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

Step 4: Calculate factorial(3) step-by-step:

factorial(3) calls 3 * factorial(2)
factorial(2) calls 2 * factorial(1)
factorial(1) calls 1 * factorial(0)
factorial(0) returns 1 (base case)
factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6

Answer: \( 3! = 6 \)

graph TD    A[factorial(3)]    B[factorial(2)]    C[factorial(1)]    D[factorial(0)]    A --> B    B --> C    C --> D    D -->|returns 1| C    C -->|returns 1| B    B -->|returns 2| A    A -->|returns 6| End

Worked Example 2: Fibonacci Series Using Recursion Medium

Example 2: Fibonacci Series Using Recursion Medium

Find the 4th Fibonacci number using recursion. The Fibonacci sequence starts with 0 and 1, and each number is the sum of the two preceding ones.

Step 1: Define base cases:

F(0) = 0
F(1) = 1

Step 2: Define recursive case:

\( F(n) = F(n-1) + F(n-2) \) for \( n > 1 \)

Step 3: Write the recursive function:

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

Step 4: Calculate fibonacci(4) step-by-step:

fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)
fibonacci(1) = 1 (base case)
fibonacci(0) = 0 (base case)
Calculate upwards:

fibonacci(2) = 1 + 0 = 1
fibonacci(3) = 1 + 1 = 2
fibonacci(4) = 2 + 1 = 3

Answer: The 4th Fibonacci number is 3.

Note: This recursive method recalculates many values multiple times, leading to inefficiency.

graph TD    F4[fibonacci(4)]    F3[fibonacci(3)]    F2a[fibonacci(2)]    F2b[fibonacci(2)]    F1a[fibonacci(1)]    F1b[fibonacci(1)]    F0a[fibonacci(0)]    F4 --> F3    F4 --> F2a    F3 --> F2b    F3 --> F1a    F2a --> F1b    F2a --> F0a

Worked Example 3: Sum of Array Elements Using Recursion Medium

Example 3: Sum of Array Elements Using Recursion Medium

Write a recursive function to find the sum of all elements in the array [2, 4, 6, 8].

Step 1: Define the base case: If the array is empty, the sum is 0.

Step 2: Define the recursive case: Sum of array = first element + sum of the rest of the array.

Step 3: Pseudocode:

function sumArray(arr):    if length(arr) == 0:        return 0    else:        return arr[0] + sumArray(arr[1:])

Step 4: Calculate sumArray([2,4,6,8]):

2 + sumArray([4,6,8])
2 + (4 + sumArray([6,8]))
2 + 4 + (6 + sumArray([8]))
2 + 4 + 6 + (8 + sumArray([]))
sumArray([]) = 0 (base case)
Total = 2 + 4 + 6 + 8 + 0 = 20

Answer: The sum of the array elements is 20.

Worked Example 4: Tower of Hanoi Problem Hard

Example 4: Tower of Hanoi Problem Hard

Solve the Tower of Hanoi puzzle for 3 disks. The goal is to move all disks from peg A to peg C, following these rules:

Only one disk can be moved at a time.
A larger disk cannot be placed on top of a smaller disk.
Use peg B as an auxiliary.

Step 1: Define the base case: If there is only 1 disk, move it directly from source to destination.

Step 2: Recursive case: To move \( n \) disks from source to destination:

Move \( n-1 \) disks from source to auxiliary.
Move the largest disk from source to destination.
Move \( n-1 \) disks from auxiliary to destination.

Step 3: Pseudocode:

function towerOfHanoi(n, source, destination, auxiliary):    if n == 1:        print("Move disk 1 from", source, "to", destination)        return    towerOfHanoi(n-1, source, auxiliary, destination)    print("Move disk", n, "from", source, "to", destination)    towerOfHanoi(n-1, auxiliary, destination, source)

Step 4: Steps for 3 disks:

Move 2 disks from A to B using C
Move disk 3 from A to C
Move 2 disks from B to C using A

Answer: The sequence of moves is:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

graph TD    A1[Move n-1 disks from A to B]    A2[Move disk n from A to C]    A3[Move n-1 disks from B to C]    Start --> A1 --> A2 --> A3 --> End

Worked Example 5: Checking Palindrome Using Recursion Medium

Example 5: Checking Palindrome Using Recursion Medium

Write a recursive function to check if the string "radar" is a palindrome. A palindrome reads the same forwards and backwards.

Step 1: Define base cases:

If the string length is 0 or 1, it is a palindrome.

Step 2: Recursive case:

Check if the first and last characters are the same.
If yes, recursively check the substring without the first and last characters.
If no, it is not a palindrome.

Step 3: Pseudocode:

function isPalindrome(s):    if length(s) <= 1:        return True    if s[0] != s[-1]:        return False    return isPalindrome(s[1:-1])

Step 4: Check "radar":

Compare 'r' and 'r' -> same
Check "ada"
Compare 'a' and 'a' -> same
Check "d"
Length is 1 -> palindrome

Answer: "radar" is a palindrome.

Formula Bank

Factorial

\[ n! = \begin{cases} 1 & \text{if } n=0 \\ n \times (n-1)! & \text{if } n>0 \end{cases} \]

where: \( n \) = non-negative integer

Fibonacci Sequence

\[ F(n) = \begin{cases} 0 & \text{if } n=0 \\ 1 & \text{if } n=1 \\ F(n-1) + F(n-2) & \text{if } n>1 \end{cases} \]

where: \( n \) = position in the sequence (non-negative integer)

Sum of First n Natural Numbers

\[ S(n) = \begin{cases} 0 & \text{if } n=0 \\ n + S(n-1) & \text{if } n>0 \end{cases} \]

where: \( n \) = non-negative integer

Tips & Tricks

Tip: Always define a clear base case to prevent infinite recursion.

When to use: When writing any recursive function.

Tip: Use recursion trees or flowcharts to visualize recursive calls and understand the process.

When to use: When debugging or learning recursion.

Tip: For problems with overlapping subproblems (e.g., Fibonacci), use memoization or dynamic programming to optimize.

When to use: When recursion leads to repeated calculations and inefficiency.

Tip: Tail recursion can be optimized by some compilers to reduce stack usage.

When to use: When writing recursive functions that can be converted to tail recursion.

Tip: Trace small inputs manually to understand recursion flow before coding.

When to use: When starting to solve a new recursive problem.

Common Mistakes to Avoid

❌ Not defining or incorrectly defining the base case, causing infinite recursion.

✓ Always include a base case that stops recursion when a simple condition is met.

Why: Students often forget the stopping condition or set it incorrectly.

❌ Confusing the recursive case with the base case.

✓ Clearly separate the base case (termination) and recursive case (progression).

Why: Misunderstanding leads to incorrect function logic.

❌ Ignoring the cost of recursive calls leading to stack overflow.

✓ Analyze recursion depth and optimize with tail recursion or iterative methods if needed.

Why: Students underestimate memory and time complexity.

❌ Using recursion where iteration is more efficient without justification.

✓ Choose recursion only when it simplifies the problem or is required; otherwise, use loops.

Why: Recursion can be less efficient and harder to debug.

❌ Not handling edge cases like zero or negative inputs in recursive functions.

✓ Include input validation and appropriate base cases for all input ranges.

Why: Leads to runtime errors or infinite recursion.

Key Concept

Recursion Essentials

Recursion solves problems by calling the same function on smaller inputs until reaching a base case that stops the recursion.

The Joy of Learning

Login

The Joy of Learning

Sign-up

The Joy of Learning

Forgot Password

Introduction to Recursion

Definition and Structure of Recursive Functions

Types of Recursion

Worked Example 1: Calculating Factorial Using Recursion Easy

Worked Example 2: Fibonacci Series Using Recursion Medium

Worked Example 3: Sum of Array Elements Using Recursion Medium

Worked Example 4: Tower of Hanoi Problem Hard

Worked Example 5: Checking Palindrome Using Recursion Medium

Formula Bank

Tips & Tricks

Common Mistakes to Avoid

Recursion Essentials

Try Practice next.

Rank

eBook

Online Test Series + eBook

Book is added to your cart!