## FRACTALS USING RECURSION PROGRAMMING:

**Recursion** is a process which evaluates an object in terms of a simpler case of itself is called Recursion. The recursive algorithm invocation must eventually reduce to some computation of one or more simplest possible, non-recursive cases. Every Recursion contain the most simplest result or exit point. This scenario or condition which evaluates to simplest possible solution is known as base case. The other part of the algorithm is called as recursive case.

#### 1. Functional Recursion

#### 2. Procedural Recursion

The recursive algorithm if it involves multiple functions/methods to do recursion then it is called Recursive Chain.

All recursion simulation follow a simple pattern solution implemented recursively. Recursion is not always inefficient. Recursion should be used

**If we can express the simplest possible case i.e. exit point with clear, direct and elegant code.****If we can logically design a task that follows recursive steps.****If we can provide better solution through recursive process then any other process for e.g. iterative process**.

Recursive simulation can be optimized using partial exploration technique of exhaustive recursion. For e.g. A letter combination from a given set of letters to create a new valid word found in scramble dictionary, We can apply recursive process but as the no of letters increase so the choices of selecting the letter increases as well as the depth of the decision tree increases. For every new letter added to the set of letters the depth of decision tree increases by N! and no of choices or decision taken to select a letter increase by 2 raised to N. So the recursion becomes very exhaustive. To avoid this situation we need to use the partial exploration technique of exhaustive recursion. For e.g. to compute the value of 2 raised to 10 we don’t need to recursively compute 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2, we just need to compute 2 * 2 * 2 * 2 * 2 and add it twice, in this way we have optimized the recursive code.

### Recursive Backtracking Approach

There is one more recursive technique to resolve problems with complex iteration known as Recursive Backtracking. The application of recursive backtracking to a problem is as follows

**– Cast problem in terms of decision points. (i.e. Choosing between different options.) **

**– Identify what decision needs to be made. so that decision helps in moving forward towards the resolution or the exit point. **

**– A recursive call makes one decision and recurs on the remaining decisions. **

**– Design recursion function to return success or failure. **

**– At each call, choose one option and go with it. **

**– Recursively proceed and see what happens if you can reach the base case or not. **

**– If it is successful then implement the required base case conclusion else if it is unsuccessful then unmake the decision and try another option. **

**– If no option worked, all options were exhausted to failure return failure result which triggers backtracking.(i.e. unmaking of earlier decisions).**

The best examples of recursive backtracking are

###### 1. Sudoku Game.

###### 2. N Queens on a chess board.

###### 3. Towers of Hanoi. Recursion Backtracking Pseudocode

bool Solve( configuration conf)

{

if(no more choices)

return configuration is the required goal.

for(all available choices)

{

try one option O;

Solve the case if it works then mark it as done.

Otherwise unmake the option you made for the current move

}

tried all options no solution found,

so return false.

}

The Subset strategy of recursion: Suppose we have N elements in a set. We need to choose k elements from that set. Then we have combination equal to C(n,k). Number of subset that include desired event/option is C(n-1,k-1). Number of subset that do not include desired event/option is C(n-1,k). Do Recursion (n , k) { if(k==0 || k==n) return 1. else return Combination C(n-1,k) + C(n-1,k-1) }

Tower of Hanoi is one of the greatest examples of Implementation of Recursive Backtracking Technique.