Java Recursion

Java Recursion

Recursion is when a method calls itself. It is a way to break a problem into smaller copies of itself.

Recursion example

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }

  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

This adds 10 + 9 + 8 + ... + 1.

The stopping condition

Recursion needs a base case that stops the calls. In the example, when k is not greater than 0, the method returns 0 instead of calling itself.

How the calls stack

sum(10) calls sum(9), which calls sum(8), and so on, until sum(0) returns 0. Then the values add up as each call returns.

Halting problem

Every recursive method must have a condition that eventually stops it. Without one, the program runs forever and crashes with a stack overflow.

TL;DR

• Recursion is a method calling itself.
• Always include a base case to stop.
• Use it for problems that break into smaller versions of themselves.