Recursion

The process in which a method calls itself is called recursion.

Recursion occurs when a method calls itself.

Example: a method calling itself

Method1()
{
 Method1();
}

Recursion is used to solve the problem where the solution of a problem depends on the solution of the smaller instances of the same problem

For example we are trying to find factorial of 5.

problem: factorial(5)

factorial(5) = 5* Factorial(4)

to find the solution for factorial(5), we need to find solution for another smaller instance of same problem Factorial(4).

Factorial(4) = 4 * factorial(3)

to find the solution for factorial(4), we need to find solution for another smaller instance of same problem Factorial(3).

similarly

Factorial(3) = 3 * factorial(2)

Factorial(2) = 2 * factorial(1)

Factorial(1) = 1 * factorial(0)

factorial(0) = 1

once terminal condition or base condition occurs, it is the end of recursion.
from this point there is no recursion. and it return the value of that condition.

here in this example  factorial(0) returns 1. and the execution continues

Factorial(1) = 1 * 1  // as factorial(0) = 1

Factorial(2) = 2 * 1  // as Factorial(1) = 1

Factorial(3) = 3 * 2  // as Factorial(2) = 2

Factorial(4) = 4 * 6  // as Factorial(3) = 6

Factorial(5) = 5 * 24 // as Factorial(4) = 24

final out put for Factorial(5) is 120.

factorial(5)
 = (5* Factorial(4))
 = (5* (4 * Factorial(3)))
  =(5* (4 * (3 * Factorial(2))))
   = (5* (4 * (3 * (2 * Factorial(1)))))
    = (5* (4 * (3 * (2 * (1 * Factorial(0))))))
    = (5* (4 * (3 * (2 * (1 * 1)))))
   = (5* (4 * (3 * (2 * 1))))
  = (5* (4 * (3 * 2)))
 = (5* (4 * 6))
=(5 * 24)

= 120

The recursion can be direct (when the method calls itself) or indirect (when the method calls some other method that then calls the first method).

Direct Recursion:
Method1()
{
 Method1()
}

Indirect Recursion:
Method1()
{
 Method2()
}

Method2()
{
 Method1()
}

Recursion can also be single (when the method calls itself once) or multiple (when the method calls itself multiple times).

Examples:
Factorial
Fibonacci series
GCD
Tower Of Hanoi