🎓 A1Learner
🔍

Java Recursion

Recursion is a technique where a method calls itself to solve a problem in smaller steps. Each call works on a smaller input than the call before it.

Count down to zero

The countdown method prints its number and then calls itself with one less. The call with 0 prints 0 and makes no further call.

public class Main {
  static void countdown(int n) {
    if (n == 0) {
      System.out.println(0);
    } else {
      System.out.println(n);
      countdown(n - 1);
    }
  }

  public static void main(String[] args) {
    countdown(3);
  }
}

Add numbers with recursion

The sum method returns its number plus the sum of the numbers below it. The call with 0 returns 0 and stops the chain.

public class Main {
  static int sum(int n) {
    if (n == 0) {
      return 0;
    }
    return n + sum(n - 1);
  }

  public static void main(String[] args) {
    System.out.println(sum(5));
  }
}

Example

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

  public static void main(String[] args) {
    System.out.println(factorial(5));
  }
}

Key points

  • A recursive method calls itself inside its own body.
  • Each call receives a smaller input than the call before it.
  • A base case is the condition that stops the calls.
  • Without a base case, the calls never stop.
  • A recursive method can return a value from each call.

In this example, factorial calls itself with a smaller number each time. The call with 1 returns 1 and stops the chain. Each waiting call multiplies its own number by the result it receives. The final product is 120.

Note

Recursion suits problems that split into smaller copies of the same problem.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Programiz Java Compiler

Exercise

What does a base case do in a recursive method?