14 Java Fundamentals | Recursion in Java | By Dummy for Dummies

By -

 

INTRODUCTION

Imagine you want to make a method that has to do a complex task which cannot be done in a single call. In that case, you can break the task into smaller parts: the method will do a small portion, then call itself again to handle the next part, and so on, until the desired result is reached


RECURSION

A recursive method is more like a loop. It will call itself and repeat the same process. We will manually set some conditions for when to stop this whole process, and what to pass as arguments when the method call itself again.

Base Case.
Base case is the most important part of recursive method.It is the condition which will decide when to stop the process. Without this the recursive method will keep on calling itself until the program CRASHES!
It consists of a single if condition which when comes true the recursion will stop

Correct Call
We will set the call inside the method itself, and set the arguments in such way that each time it call itself it sends updated data not the original

Progress
Each time the recursive method call itself, it should get more closer toward the condition of base case. If it does not, then the Base case will never come true and the program will eventually crash.

Memory Use
Unlike loops, recursion use a lot of memory, so avoid unnecessary calls or too much recursion will crash the program. The high use of memory is the reason why infinite recursion crashes but infinite loop doesn't.


DEMONSTRATION

Let's demonstrate working of a pistol. Suppose it has 8 bullets per magazine. The gun is automatic, means you fire first bullet, it will reload the next bullet and fire it, until all bullets are fired.

So when we make call for first bullet, inside from that method it will call itself again but the number of bullets must decrease. And there must be a condition that if bullets become zero it should stop.

CODE:



public class Main{

    public static void main(String[] args) {
        int bullets = 8; // starting bullets
        System.out.println("Starting firing with " + bullets + " bullets...");
        fireBullets(bullets );
        System.out.println("Project Completed!");

    }

    // Recursive method to fire bullets
    public static void fireBullets(int bullets) {
        // Base case: stop when no bullets left
        if (bullets == 0) {
            System.out.println("Out of bullets. Reload required!");
            return;
        }

        // Action for this call
        System.out.println("FIRED BULLET!");
        bullets--;
        System.out.println("Bullets left: " + bullets );

        // Recursive call with one less bullet
        fireBullets(bullets);
        System.out.println("Ending method. It was called when bullet were "+bullets);
    }
}

EXPLANATION

⦿ The  main  method calls the  fireBullets()  method. And send number of bullets as argument

⦿ The  fireBullets()  recieve integer 8, store it in parameter  bullets .

⦿ First, the method checks  if(bullets == 0) . Since it is 8, this part is ignored and code proceeds

⦿ It prints FIRED BULLET! and number of bullets is decremented i.e. from 8 to 7

⦿ Then it prints that 7 bullets are left

⦿ Before the method ends, it calls itself again and pass integer 7 as argument, instead of 8

⦿ This whole process continues until the the bullet becomes 0. Then integer 0 will be sent as argument.

⦿ The method will check  if(bullets == 0) . Since it is true, the code inside condition will be executed

⦿ It will print Out of bullets....and return.

⦿ But since no method actually ended and called itself before completion. Therefore they are all stacked over each other and now return in reverse pattern and end method. Here's the output.

OUTPUT:
Starting firing with 8 bullets... FIRED BULLET! Bullets left: 7 FIRED BULLET! Bullets left: 6 FIRED BULLET! Bullets left: 5 FIRED BULLET! Bullets left: 4 FIRED BULLET! Bullets left: 3 FIRED BULLET! Bullets left: 2 FIRED BULLET! Bullets left: 1 FIRED BULLET! Bullets left: 0 Out of bullets. Reload required! Ending method. It was called when bullet were 1 Ending method. It was called when bullet were 2 Ending method. It was called when bullet were 3 Ending method. It was called when bullet were 4 Ending method. It was called when bullet were 5 Ending method. It was called when bullet were 6 Ending method. It was called when bullet were 7 Ending method. It was called when bullet were 8 Project Completed! 

REAL PROBLEM SOLVING (Factorial)

Let's find factorial of a number using recursion. Factorial of a number means product of all numbers from 1 up to that specific number. 

                  e.g. 5! = 5 x 4 x 3 x 2 x 1

                  e.g. 4! = 4 x 3 x 2 x 1

                  e.g. 3! = 3 x 2 x 1

We can see a pattern:
5 = 5 x 4!
4 = 4 x 3!
... and at the end, 1! = 1


LOGIC:

⦿ The user gives starting value, e.g. n = 5

⦿ We also know that factorial always ends at 1. So when we reach 1 just return it and stop further calls (This is our base case)

⦿ From the above example we can draw an equation for factorial i.e. n! = n x (n-1)!

⦿ So when we call the method again we send n-1 as argument. There it will become n, and again it will send n-1

⦿ It will look something like this:
 factorial(5)  return →   5 * factorial(5-1)  
 factorial(4)  return →   4 * factorial(4-1)  
 factorial(3)  return →   3 * factorial(3-1)  
 factorial(2)  return →   2 * factorial(2-1)  
 factorial(1)  return →   1   and stop further call (Base case)

⦿ The calculation will occur in reverse i.e.:
 factorial(1)  = 1   → returned to   factorial(2)  
 factorial(2)  = 2 * 1 = 2   → returned to   factorial(3)  
 factorial(3)  = 3 * 2 = 6   → returned to   factorial(4)  
 factorial(4)  = 4 * 6 = 24  → returned to   factorial(5)  
 factorial(5)  = 5 * 24 = 120 → returned to   main   method

⦿ Final Answer: 120 will be printed in the main method.


CODE:


public class Main {
    public static void main(String[] args) {
        int number = 5;  // Example input
        int result = factorial(number);
        System.out.println("Factorial of " + number + " is: " + result);
    }

    // Recursive method to calculate factorial
    static int factorial(int n) {
        if (n <= 1) {   // Base case
            return 1;
        }
        return n * factorial(n - 1);  // Recursive case
    }
}

OUTPUT:
Factorial of 5 is: 120


EXERCISE

Let's do an exercise for what we studied in this post. Study this code, break it down, analyze it and identify the concepts used here. It would be even better if you write down your observations and make a mini report on it.

CODE


import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        // Asking the user for numbers
        System.out.print("Enter a number to find its factorial: ");
        int num1 = sc.nextInt();

        System.out.print("Enter a number to print its countdown: ");
        int num2 = sc.nextInt();

        System.out.print("Enter a number to calculate sum of natural numbers: ");
        int num3 = sc.nextInt();

        System.out.print("Enter a base number: ");
        int base = sc.nextInt();
        System.out.print("Enter an exponent: ");
        int exp = sc.nextInt();

        // Calling recursive methods
        int factResult = factorial(num1);
        countdown(num2);
        int sumResult = sumNatural(num3);
        int powerResult = power(base, exp);

        // Displaying results
        System.out.println("Factorial of " + num1 + " = " + factResult);
        System.out.println("Sum of first " + num3 + " numbers = " + sumResult);
        System.out.println(base + " raised to " + exp + " = " + powerResult);

        sc.close();
    }

    // 1. Factorial using recursion
    public static int factorial(int n) {
        if (n <= 1) return 1;   // Base case
        return n * factorial(n - 1);  // Recursive case
    }

    // 2. Countdown using recursion
    public static void countdown(int n) {
        if (n < 0) return;  // Base case
        System.out.println("Countdown: " + n);
        countdown(n - 1);   // Recursive call
    }

    // 3. Sum of natural numbers using recursion
    public static int sumNatural(int n) {
        if (n <= 0) return 0;   // Base case
        return n + sumNatural(n - 1); // Recursive case
    }

    // 4. Power function using recursion
    public static int power(int base, int exp) {
        if (exp == 0) return 1;   // Base case
        return base * power(base, exp - 1);  // Recursive case
    }
}

OUTPUT:

Enter a number to find its factorial: 4

Enter a number to print its countdown: 5

Enter a number to calculate sum of natural numbers: 6

Enter a base number: 2

Enter an exponent: 4

Countdown: 5

Countdown: 4

Countdown: 3

Countdown: 2

Countdown: 1

Countdown: 0

Factorial of 4 = 24

Sum of first 6 numbers = 21

2 raised to 4 = 16

MINI PROJECT (Monkey’s Banana Counter)

Boss Monkey wants to count bananas in a recursive way instead of using loops. You will create a small program that solves two tasks using recursion.


Tasks

⦿ Create a class BananaCounter.

⦿ Implement two recursive methods:

1.  countdown(int n)  → prints numbers from n down to 1, then prints "No bananas left!".

2.  sumBananas(int n)  → returns the sum of bananas from 1 to n.

⦿ In the main method:

1. Ask the user to enter a number.

2. Call both recursive methods.

3. Print the results neatly.


Example Output:

Enter number of bananas: 5


Countdown:

5

4

3

2

1

No bananas left!


Total bananas collected = 15

CLOSING

That’s it for recursion in Java! Recursion lets a method call itself to solve problems step by step, until it reaches a simple condition (the base case). It’s powerful for breaking down big problems into smaller ones.

One call, many steps, that’s the power of recursion.