**Recursion** is referred to a programming style where a **method invokes itself** repeatedly until a certain predefined condition is met. Such method calls are also called **recursive methods**.

## 1. Syntax of recursive methods

A recursion based method MUST two basic components to solve a problem correctly.

- recursive method call
- a precondition which break the recursion

Please keep in mind that if precondition is not reachable or not defined, then stack overflow problem will happen.

method(T parameters...) { if(precondition == true) //precondition { return result; } return method(T parameters...); //recursive call }

## 2. Recursion Types

Recursion are of two types based on when the recursive method call is made.

#### 1. Tail recursion

A recursive method is **tail recursive** when recursive method call is the last statement executed inside the method (usually along with a **return statement**).

method(T parameters...) { if(precondition == true) { return result; } return method(T parameters...); }

#### 2. Head recursion

Any recursion which is not tail recursion, can be referred as head recursion.

method(T parameters...) { if(some condition) { return method(T parameters...); } return result; }

## 3. Java recursion examples

#### 3.1. Fibonacci Series

Fibonacci series is a sequence of numbers where each number is defined as the sum of the two numbers proceeding it.

For example – 1, 1, 2, 3, 5, 8, 13, 21, 34 and so on…

This function gives us the Fibonacci number at nth position starting from 1.

public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

Let’s test this function to print the fibonacci series upto n = 10;

public static void main(String[] args) { int number = 10; for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " "); } }

Program output.

1 1 2 3 5 8 13 21 34 55

#### 3.2. Fibonacci Series

The *greatest common divisor* (gcd) of two positive integers is the largest integer that divides evenly into both of them.

public static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); }

Let’s test this function to print the fibonacci series upto n = 10;

public static void main(String[] args) { int number1 = 40; int number2 = 500; System.out.print( gcd(number1, number2) ); }

Program output.

20

Let me know your questions related to **recursion in Java**.

Happy Learning !!