Computer

# Recursion

## Recursion

Process of solving a problem by reducing it to smaller versions of itself.

## Difference between Iteration and Recursion

 ITERATION RECURSION Requires less memory. Requires large memory. It is a fast process. It is a slow process.

• For a recursive function, you only need to define the base case and recursive case, so the code is simpler and shorter than an iterative code.
• Some problems are inherently recursive, such as Graph Tree Traversal.

• A recursive program has greater space requirements than an iterative program as each function call will remain in the stack until the base case is reached.
• It also has greater time requirements because each time the function called, the stack grows and the final answer is returned when the stack is popped completely.

void A()

{

………..

}

void A()

{

B();

}

void B();

{

A();

}

## Recursive Methods

• A method in java that calls itself is called the recursive method.
• Recursion is a programming technique in which a call to a method appears in that method’s body i.e., a method calls itself: this is called direct recursion.
• It works on the principle of LIFO ( Stack data structure).

## The Two Basic Cases of Recursive Methods

Base case: Any pre-known value /condition before beginning process/calculation/task. It is used to terminate the recursive process. Example: Any number to the power 0 is 1.

Recursive case: The repetitive condition of a recursive method. Method call which can call itself.

## Classification of Recursive Methods

### Finite Recursion

A recursive method having one or more base cases and is reachable or attainable.

void finite( int n)

{

if(n>0)

{

System.out.println(n);

finite(–n);

System.out.println(n);

}

}

OUTPUT: When n=3

3

2

1

0

1

2

### Infinite Recursion

A recursive method which has no base case OR the base case is not reachable/attainable.

void infinite( int n)

{

if(n>0)

{

System.out.println(n);

infinite(n-);

System.out.println(n);

OUTPUT: Infinite (never ending – error)

### Augmented Recursion

In augmented recursion, the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function)

void augmented( int n)

{

if(n>0)

{

augmented(-n);

System.out.println(n);

}

}

OUTPUT: When n=3

0

1

2

### Tail Recursion

A recursive method in which the last statement executed is the recursive call. is the recursive call. The processing occurs before the recursive call.

void tail( int n)

{

if(n>0)

{

System.out.println(n);

}

}

OUTPUT: When n=3

3

2

1