Day 13 of 60 Days of DSA: Recursion

Day 13 of 60 Days of DSA: Recursion

Understanding recursion through two fundamental problems and their code demonstrations

Recursion is one of the most important tools in a software engineer’s algorithm toolbox. Recursion is one of the most important topics for cracking coding interviews. At its core, recursion is a technique where a function solves a problem by calling itself on smaller instances of that problem — until it reaches a base case that stops further calls.

In this article, we’ll explore recursion with two classic examples:

1. Tower of Hanoi
2. Palindrome Check

Note: For better understanding of concepts go through the notes as well

Problem 1: Tower of Hanoi

Problem Description:

In the classic problem of the Towers of Hanoi, you have 3 towers numbered from 1 to 3 (left to right) and A disks numbered from 1 to A (top to bottom) of different sizes which can slide onto any tower.

The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one).

You have the following constraints:

1. Only one disk can be moved at a time.
2. A disk is slid off the top of one tower onto another tower.
3. A disk cannot be placed on top of a smaller disk.
4. You have to find the solution to the Tower of Hanoi problem.
5. You have to return a 2D array of dimensions M x 3, where M is the minimum number of moves needed to solve the problem.
6. In each row, there should be 3 integers (disk, start, end), where:

disk — number of the disk being moved
start — number of the tower from which the disk is being moved
end — number of the tower to which the disk is being moved

Example Input

Input 1:

A = 2

Input 2:

A = 3

Example Output

Output 1:

[1 1 2 ] [2 1 3 ] [1 2 3 ]

Output 2:

[1 1 3 ] [2 1 2 ] [1 3 2 ] [3 1 3 ] [1 2 1 ] [2 2 3 ] [1 1 3 ]

Example Explanation

Explanation 1:

1. We shift the first disk to the middle tower.
2. We shift the second disk to the last tower.
3. We, finally, shift the first disk from the middle tower to the last tower.

Explanation 2:

We can see that this was the only unique path with minimal moves to move all disks from the first to the third tower.

Intuition

With three rods given we need to move all the rings from start to end using helper rods. If we think in terms of recursion, we can move the first n-1 rods to the helper from the start and then the nth rod to the end from the start and then move the n-1 rods to the end from the helper using the start rod.

Let’s understand via the example of 3 rings in 3 steps:-

Step 1: If we have 3 rings, we need to move 2 (n-1) rings to the helper first from the start, using the end.

1st ring = start -> end

2nd ring = start -> helper

1st ring(back to helper) = end -> helper

Step 2: Now both 1, 2 rings are on the helper rod, so we can move our biggest ring to the end rod.

3rd ring = start -> end

Step 3: Now we need to move back n-1 rings, i.e, 2 rings from the helper to the end using the start

1st ring = helper => start

2nd ring = helper => end

1st ring = start => end

Now all the rings are end rods

Code (JavaScript)

function towerOfHanoi(n){
 let arr = []
 function towerOfHanoiHelper(start, dest, helper, n){
 if(n==0) return;
 towerOfHanoiHelper(start, helper, dest, n-1);
 arr.push([n, start, dest]);
 towerOfHanoiHelper(helper, dest, start, n-1);
 
 }
 towerOfHanoiHelper(1, 2, 3, n);
 return arr;
}

Complexities:

• Time Complexity — O(2^n)

• Space Complexity — O(n)

Problem 2: Check if a string is a Palindrome

Problem Description

Write a recursive function that checks whether string A is a palindrome or Not.
Return 1 if the string A is a palindrome, else return 0.

Note: A palindrome is a string that’s the same when read forward and backward.

Example Input

Input 1:

A = “naman”

Input 2:

A = “strings”

Example Output

Output 1: 1

Output 2: 0

Example Explanation

Explanation 1:

“naman” is a palindromic string, so return 1.

Explanation 2:

“strings” is not a palindrome, so return 0.

What’s a Palindrome?

A palindrome is a word that reads the same forward and backwards — like “abba” or “aba”. The idea is to check if the first and last character match, and then confirm that the inside substring is also a palindrome.

Using recursion, we compare characters at the ends and then move inward.

Intuition

If we take 2 pointers one on start of the string and one at the end, if two characters are same then increment the start pointer and decrement the end pointer to check the complete string in the similar manner.

Code (JavaScript)

function isPalindrome(A, i, j){
 if(i>=j) return true;
 if(A[i] == A[j]){
 return isPalindrome(A, i+1, j-1);
 }
 return false;
}

Complexities:

Time Complexity — O(n)

Space Complexity — O(n)

Key Takeaways

Recursion shines in problems where a solution can be built by solving smaller versions of the same problem.

• Tower of Hanoi captures how a large problem can be split into two smaller recursive calls with a simple base case.
• Palindrome check uses recursion to progressively reduce the problem size while checking symmetry.

Both examples help reinforce how thinking recursively can make complex problems easier to express and solve.

Do you want to solve more with us?

Then follow this series and share your progress in the comments.

If the topics are difficlt for you to understand, then you can refer to the notes on my GitHub.

Here’s the Code link

At Dev Simplified, We Value Your Feedback 📊

👉 Let us know how you’re finding this series so far. It motivates us to write and provide valuable content for you.

👉 Follow us to not miss any updates.

👉 Subscribe for free and join our growing community!