Day 15 of 60 Days of DSA — Recursion III

Magic Number: A Simple Problem That Tests Your Recursive Thinking

When people hear recursion, they often imagine complex problems like tree traversals or backtracking.
But interviews frequently test recursion using very simple-looking problems — ones that reveal whether you truly understand base cases and recursive flow.

Today’s problem, Magic Number, is a classic example.

At first glance, it looks like basic digit manipulation.
But the moment you’re asked to repeat the process until a single digit remains, recursion becomes the most natural solution.

Problem Statement:

Given a number A, check if it is a magic number or not.

A number is said to be a magic number if the sum of its digits is calculated till a single digit recursively by adding the sum of the digits after every addition. If the single digit comes out to be 1, then the number is a magic number.

Example Input

Input 1:

A = 83557

Input 2:

A = 1291

Example Output

Output 1:

1

Output 2:

0

Example Explanation

Explanation 1:

Sum of digits of (83557) = 28

Sum of digits of (28) = 10

Sum of digits of (10) = 1.

Single digit is 1, so it’s a magic number. Return 1.

Explanation 2:

Sum of digits of (1291) = 13

Sum of digits of (13) = 4

Single digit is not 1, so it’s not a magic number. Return 0.

Recursive Intuition (Explained Simply)

Let’s break the logic into two ideas:

1. Base Case

If the number is already a single digit, return it.

if (A <= 9) return A;

This stops recursion.

2. Recursive Case

If the number has more than one digit:

Calculate the sum of its digits
Call the same function again on the resulting sum

This keeps reducing the number until it becomes a single digit.

function main(A){
 return sumDigits(A) === 1 ? 1 : 0;
}

function sumDigits(A){
 if(A <= 9) return A;

 let sum = 0;
 while(A > 0){
 sum += A % 10;
 A = Math.floor(A / 10);
 }

 return sumDigits(sum);
}

How the Recursion Works (Call Flow)

For A = 83557:

sumDigits(83557)
 → sumDigits(28)
 → sumDigits(10)
 → sumDigits(1)

Time & Space Complexity

Time Complexity

Each digit is processed once per recursive call
The number quickly reduces
Overall complexity is O(d), where d isthe number of digits

Space Complexity

Recursive stack depth is small
O(log A) in the worst case

Final Takeaway

The Magic Number problem proves an important lesson:

Recursion is not about complexity — it’s about clarity of flow.

Do you want to solve more with us?

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

If the topics are difficult 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!