DAY 4 : Understanding Recursion in DSA | My DSA Journey (Recursion)

---

Introduction

Welcome to Day 4 of my DSA Journey!
For the past few days, I’ve been focusing on one of the most fundamental and important concepts in DSA — Recursion.

I’m documenting my journey in public to stay consistent and to help others who are also learning DSA from scratch.

Here’s what I learnt in last 3 days:

• Day 1:
  → What is Recursion?
  → Why do we use Recursion?
  → What is a Base Case in Recursion?
  → How a recursive function works internally (Call Stack)

• Day 2:
  → Solved basic recursion problems like:
  → Print 1 to N and N to 1
  → Factorial of a number
  → Sum of first N natural numbers

• Day 3:
  → Fibonacci Number
  → Sum of digits of a number
  → Product of digits of a number

Let’s break down each of these topics below 👇

---

What is Recursion?

A function that calls itself is called Recursion, until a specified condition is met.
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem.

// Example: Print numbers from 1 to N using recursion
void printNumbers(int n) {
    if (n == 0) return;        // Base Case
    printNumbers(n - 1);       // Recursive Call
    System.out.println(n);     // After recursion
}

Recursion has two parts:

• Base Case - The stopping condition that ends the recursion.
• Recursive Call - The part where the function calls itself with a smaller problem.

Why do we use Recursion?

Recursion helps us solve problems that can be broken down into smaller, similar subproblems.
It is especially useful when the structure of the problem is inherently recursive, like working with trees, graphs, or performing repetitive tasks.

Key Reasons to Use Recursion:

• Simpler Code for Complex Problems
• Breaks Down Big Problems
• Useful for Data Structures Like:
  • Trees (preorder, inorder, postorder traversal)
  • Graphs (DFS)
  • Backtracking problems (like generating subsets, permutations)
• Mirrors Real Problem Logic

But Recursion Isn't Always the Best:

Although recursion makes code elegant, it:

• Can be slower and use more memory due to function call stack.
• Can lead to stack overflow if the base case is not defined correctly.
• Sometimes an iterative solution is more efficient.

What is a Base Case in Recursion?

-> It is a condition where our recusion will stop making new calls.
-> It is a simple if condition. -> It needs to be returned.
-> A base case is the exit door from the recursive tunnel.
-> Without Base case, Function is being called again and again, it will run for infinity, It will give StackOverflow error.

How a recursive function works internally?

When a function calls itself, the system uses something called the call stack to keep track of each function call.

Behind the Scenes : Call Stack

The call stack is a memory structure where:

• Each function call is pushed onto the stack when invoked.
• Once the function completes (hits a return), it's popped off the stack.

In recursion:

• The function keeps calling itself → the stack gets deeper.
• When the base case is reached, the function starts returning back → the stack starts unwinding.

// Recursive Function to Print Numbers
void printNumbers(int n) {
    if (n == 0) return; // base case
    System.out.println(n);
    printNumbers(n - 1); // recursive call
}

// function call flow for printNumbers(3)
printNumbers(3)
  → prints 3
  → calls printNumbers(2)
     → prints 2
     → calls printNumbers(1)
        → prints 1
        → calls printNumbers(0)
           → base case hit → returns
        → returns
     → returns
  → returns

Q. Print 1 to N:

We want to print numbers from 1 up to N using recursion.

Approach:

• This is a forward counting problem using recursion.
• We first move deep into the recursion (from 1 to N), and only print while coming back (after the recursive call).
• The base case is when n == 0, which means we've gone below 1 and we stop.
• We first call recursively on n - 1, and after the call, we print n.

void printOneToN(int n) {
    if (n == 0) return; // base case
    printOneToN(n - 1); // recursive call
    System.out.println(n); // print after recursion
}

Q. Print N to 1:

We want to print numbers from N down to 1 using recursion.

Approach:

• We use recursion to count backward from N to 1.
• This time, we print first, then make the recursive call.
• The base case is when n == 0, which stops the recursion.

void printNtoOne(int n) {
    if (n == 0) return; // base case
    System.out.println(n); // print before recursion
    printNtoOne(n - 1); // recursive call
}

Q. Factorial of a number:

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.

Approach:

• The factorial of a number n is defined as:
  n! = n × (n-1) × (n-2) × ... × 1

• We solve this recursively by:

  • Multiplying n with the factorial of (n-1)
  • Recursively going down until we reach the base case.

• The base case is when:

  • n == 0 or n == 1, because
    0! = 1 and 1! = 1

int factorial(int n) {
    if (n == 0 || n == 1) return 1; // base case
    return n * factorial(n - 1);    // recursive step
}

Q. Sum of First N Natural Numbers:

We have to find the sum of First N Natural Numbers.

Approach:

To find the sum of the first N natural numbers, we can use recursion by following these steps:

1. Base Case:
   If N is 1, then the sum is simply 1.

2. Recursive Case:
   For any number N > 1, the sum of the first N numbers is N plus the sum of the first N-1 numbers.
   That is:
   sum(N) = N + sum(N - 1)

int sum(int N) {
        // Base case
        if (N == 1) {
            return 1;
        }
        // Recursive case
        return N + sum(N - 1);
}

Q. Fibonacci Number:

The Fibonacci sequence is a series of numbers where:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n ≥ 2

Approach:

To solve this using recursion:

1. Base Case:

   • If n == 0, return 0
   • If n == 1, return 1

2. Recursive Case:

   • For n > 1, return fibonacci(n - 1) + fibonacci(n - 2)

public static int fibonacci(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

Q. Sum of digits of a number:

We have to find the sum of digits of a number.

Approach:

To calculate the sum of digits of a number using recursion:

1. Base Case:

   • If the number becomes 0, return 0.

2. Recursive Case:

   • Extract the last digit using n % 10.
   • Call the function recursively for the remaining digits using n / 10.
   • Add the result of the recursive call to the last digit.

public static int sumOfDigits(int n) {
        // Base case
        if (n == 0) return 0;

        // Extract last digit and make recursive call
        return (n % 10) + sumOfDigits(n / 10);
    }

Q. Product of digits of a number:

We have to find the product of digits of a number.

Approach:

To calculate the product of digits of a number using recursion:

1. Base Case:

   • If the number becomes 0, return 1 (multiplicative identity).
   • If any digit is 0, the entire product becomes 0, so handle this appropriately if needed.

2. Recursive Case:

   • Extract the last digit using n % 10.
   • Call the function recursively for the remaining digits using n / 10.
   • Multiply the last digit with the result of the recursive call.

public static int productOfDigits(int n) {
        // Base case
        if (n == 0) return 0;  // product of digits of 0 is 0
        if (n < 10) return n;  // single digit case

        // Recursive case
        return (n % 10) * productOfDigits(n / 10);
    }

What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days
• Also learning Web Development — check out my [Web Dev Journey Blog].(https://ritikwebdev.hashnode.dev/day-4-react-elementjsxbabelcomponentprops-my-web-dev-journey-reactjs)
• You can follow my journey on X (Twitter) where I post regular updates.

Conclusion:

In this blog, I took my first step into the world of recursion — a powerful yet sometimes tricky concept in programming. I learned:

• What recursion is and why it’s used.
• How base cases are essential to prevent infinite loops.
• How recursive functions work behind the scenes with call stacks.
• And most importantly, I solved some classic problems using recursion:
  • Printing numbers from 1 to N
  • Calculating factorial of a number
  • Finding sum and product of digits
  • Generating Fibonacci numbers
  • Summing the first N natural numbers

This journey helped me understand how breaking down a problem into smaller subproblems can lead to elegant solutions.

I know recursion can be confusing at first, but with practice, it becomes clearer. I'm excited to keep going and dive deeper into more advanced topics like backtracking in the upcoming blogs.

If you're also starting your DSA journey, I hope this blog helps you understand recursion better. Keep learning and keep coding!

If you're on a similar journey, feel free to reach out or follow along — we’re all in this together.