Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied.

- In order to solve a problem recursively, two conditions must be satisfied. First, the problemÂ must be written in a recursive form, and second, the problem statement must include a stopping condition.

**Factorial Program using loop in java**

1 2 3 4 5 6 7 8 9 10 |
class FactorialExample{ public static void main(String args[]){ int i,fact=1; int number=5;//It is the number to calculate factorial for(i=1;i<=number;i++){ fact=fact*i; } System.out.println("Factorial of "+number+" is: "+fact); } } |

**Factorial Program using recursion in java
**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class FactorialExample2{Â Â Â static int factorial(int n){Â Â Â Â Â Â if (n == 0)Â Â Â Â Â Â Â Â return 1;Â Â Â Â Â Â elseÂ Â Â Â Â Â Â Â return(n * factorial(n-1));Â Â Â Â Â }Â Â Â Â Â public static void main(String args[]){Â Â Â int i,fact=1;Â Â Â Â int number=4;//It is the number to calculate factorialÂ Â Â Â Â Â fact = factorial(number);Â Â Â Â Â System.out.println("Factorial of "+number+" is: "+fact);Â Â Â Â Â }Â Â } |

**Application Area of Recursion**

**Method Calls ****&Â **** RecursionÂ ****implementation**

**Differences ****between recursion and iteration:**

- Both involve repetition.
- Both involve a termination test.
- Both can occur infinitely.

Iteration |
Recursion |

Iteration explicitly user a repetition structure. | Recursion achieves repetition through repeated function calls. |

Iteration terminates when the loop continuation. | Recursion terminates when a base case is recognized. |

Iteration keeps modifying the counter until the loop continuation condition fails. | Recursion keeps producing simple versions of the original problem until the base case is reached. |

Iteration normally occurs within a loop so the extra memory assigned is omitted. | Recursion causes another copy of the function and hence a considerable memory spaceâ€™s occupied. |

It reduces the processorâ€™s operating time. | It increases the processorâ€™s operating time. |

**AnatomyÂ **** of ****a Recursive call**

The function that defines raising any number *x *to a nonnegative integer power *n *is a good example of a recursive function. The most natural definition of this function is given by:

Using this definition, the value of *x*4 can be computed in the following way:

*x*4 = *x *Â· *x*3 = *x *Â· (*x *Â· *x*2) = *x *Â· (*x *Â· (*x *Â· *x*1)) = *x *Â· (*x *Â· (*x *Â· (*x *Â· *x*0)))

= *x *Â· (*x *Â· (*x *Â· (*x *Â· 1))) = *x *Â· (*x *Â· (*x *Â· (*x*))) = *x *Â· (*x *Â· (*x *Â· *x*))

= *x *Â· (*x *Â· *x *Â· *x*) = *x *Â· *x *Â· *x *Â· *x*

**TailÂ ****Â ****Recursion**

A **recursive function** is said to be **tail recursive** if there are no pending operations to be performed on return from a recursive call.Tail recursion is also used to return the value of the lastÂ Â recursive call as the value of the function.**Tail ****recursion **is advantageous as the amount of information which must be stored during computation is independent of the number of recursive calls.

**It is tail ****recursive**

1 2 3 4 5 |
void tail(int i) { if (i>0) { Â Â system.out.print(i+"") tail(i-1) } |

**Is the factorial method a tail recursive method?**

1 2 3 4 5 6 |
int fact(int x){ Â Â if (x==0) Â Â Â Â Â return 1; Â Â else Â Â Â Â Â return x*fact(x-1); } |

When returning back from a recursive call, there is still one pending operation, multiplication. Therefore, factorial is a non-tail recursive method.

**Advantage of Tail Recursive Method**

Tail Recursive methods are easy to convert to iterative.

1 2 3 4 5 6 |
void tail(int i){ Â if (i>0) { Â Â Â system.out.println(i+""); Â Â Â tail(i-1) Â } } |

>>>>

1 2 3 4 |
void iterative(int i){ Â for (;i>0;i--) Â Â Â System.out.println(i+""); } |

- Smart compilers can detect tail recursion and convert it to iterative to optimize code
- Used to implement loops in languages that do not support loop structures explicitly (e.g.Â prolog)

**Indirect ****Recursion**

- If X makes a recursive call to X itself, it is called direct recursion.
- Indirect recursive methods call themselves indirectly through calling other methods.
- In general, indirect recursion is a circular sequence of two or more recursive calls: X1 –> X2 –> … –> X1.

**Indirect Recursion Example**

Three method for decoding information are:

*receive:*stores information in buffer and calls decode.*decode:*converts information to new form and calls store*store*: stored information in a file, call receive.

We have a chain of calls:Â Â recieve() -> decode() -> store() ->recieve()-> decode()….

# NestedÂ Recursion

## ExcessiveÂ Recursion

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void IterativeFib(int n) { Â Â Â Â Â if (n < 2) Â Â Â Â Â Â Â Â Â Â Â Â return n; Â Â Â Â Â else Â Â Â Â Â { Â Â Â Â Â Â Â Â Â Â Â Â Â int i = 2, tmp, current = 1, last = 0; Â Â Â Â Â Â Â Â Â Â Â Â Â for ( ; i<=n; ++i) Â Â { Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â tmp= current; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â current += last; Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â last = tmp; Â Â Â Â Â Â Â Â Â Â Â Â Â Â } Â Â Â Â Â Â return current; Â Â Â Â Â Â } } |

# Backtracking

**History**

- Backtrackâ€™ the Word was first introduced by Dr. D.H. Lehmer in 1950s.
- R.J Walker Was the First man who gave algorithmic description in 1960.
- LaterÂ developed by S. Golamb and L. Baumert.

**Definition:-**

Backtracking is a methodical way of trying out various sequences of decisions, until you find one that â€œworks. Backtracking allows us to **systematically try** all available avenues from a certain point after some of them lead to nowhere. Using backtracking, we **can always return to a position** which offers other possibilities for successfully solving the problem.

**Advantages**

- Comparison with the Dynamic Programming, Backtracking Approach is more effective in some cases.
- Backtracking Algorithm is the best option for solving tactical problem.
- Also Backtracking is effective for constraint satisfaction problem.
- In greedy Algorithm, getting the Global Optimal Solution is a long procedure and depends on user statements but in Backtracking It Can Easily getable.
- Backtracking technique is simple to implement and easy to code.
- Different states are stored into stack so that the data or Info can be usable anytime.
- â€“The accuracy is granted.

**Disadvantages**

- Backtracking Approach is not efficient for solving strategic Problem.
- The overall runtime of Backtracking Algorithm is normally slow
- To solve Large Problem Sometime it needs to take the help of other techniques like Branch and bound.
- Need Large amount of memory space for storing different state function in the stack for big problem.
- Thrashing is one of the main problem of Backtracking.
- The Basic Approach Detects the conflicts too late.

â€“

__Application of Backtracking__

- Optimization and tactical problems
- Constraints Satisfaction Problem
- Electrical Engineering
- Robotics
- Artificial Intelligence
- Genetic and bioinformatics Algorithm
- Materials Engineering
- Network Communication
- Solving puzzles and path

**Some Problem Solved with Backtracking Technique**

- N- Queens Problem
- Sum of Subset
- Sudoku Puzzle
- Maze Generation
- Hamiltonian Cycle

**8****-Queens Problem**

**History:**

First Introduced in 1848 which was known as 8- queens Puzzle. Surprisingly, The First Solution was created in 1950 by Franz Nauck. Nauck made an 8X8 Chessboard to find the first Feasible Solution.

__Problem Description__

In a NxN square board N â€“ number of queens need to be placed considering three Condition —

- No two Queens can be placed in same row.
- No two Queens Can be places in same Column
- No two queens Can be placed in same Diagonal.