14 Java Fundamentals

Recursion in Java

By Dummy for Dummies

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 calls itself again.

Base Case

Base case is the most important part of a 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 true, the recursion will stop.

Correct Call

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

Progress

Each time the recursive method calls itself, it should get closer toward the condition of the 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 uses 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 an infinite loop doesn't.

Demonstration

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

So when we make a call for the first bullet, inside 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.

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

    public static void fireBullets(int bullets) {
        if (bullets == 0) {
            System.out.println("Out of bullets. Reload required!");
            return;
        }
        System.out.println("FIRED BULLET!");
        bullets--;
        System.out.println("Bullets left: " + bullets);
        fireBullets(bullets);
        System.out.println("Ending method. It was called when bullets were " + bullets);
    }
}

• The main method calls the fireBullets() method and sends the number of bullets as an argument.
• The fireBullets() method receives integer 8 and stores it in the parameter bullets.
• First, the method checks if(bullets == 0). Since it is 8, this part is ignored and the code proceeds.
• It prints FIRED BULLET! and the 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 passes integer 7 as an argument, instead of 8.
• This whole process continues until the bullet becomes 0. Then integer 0 will be sent as an argument.
• The method will check if(bullets == 0). Since it is true, the code inside the condition will be executed.
• It will print "Out of bullets..." and return.
• Since no method actually ended and called itself before completion, they are all stacked over each other and now return in reverse pattern and end the method.

Real Problem Solving (Factorial)

Let's find the factorial of a number using recursion. The factorial of a number means the 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 a 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: n! = n x (n-1)!
• So when we call the method again, we send n-1 as an argument. There it will become n, and again it will send n-1
• The calculation will occur in reverse: factorial(1) = 1 → factorial(2) = 2*1 = 2 → factorial(3) = 3*2 = 6 → factorial(4) = 4*6 = 24 → factorial(5) = 5*24 = 120 → returned to main

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

    static int factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}

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.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        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();

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

        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();
    }

    public static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    public static void countdown(int n) {
        if (n < 0) return;
        System.out.println("Countdown: " + n);
        countdown(n - 1);
    }

    public static int sumNatural(int n) {
        if (n <= 0) return 0;
        return n + sumNatural(n - 1);
    }

    public static int power(int base, int exp) {
        if (exp == 0) return 1;
        return base * power(base, exp - 1);
    }
}

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:
  • countdown(int n) prints numbers from n down to 1, then prints "No bananas left!".
  • sumBananas(int n) returns the sum of bananas from 1 to n.
• In the main method: Ask the user to enter a number. Call both recursive methods. Print the results neatly.

Example Output

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.