Recusion Defination

RECUSION DEFINATION

A procedure that calls itself, or invokes a series of other functions that eventually invokes the first function again, is called recursive function. The process of doing this operation is called recursion.

(Or)    

A repetitive algorithm uses recursion whenever the algorithm appears with in the definition itself.” Recursion is a repetitive process in which an algorithm calls itself.”

Example:

 Algorithm recursivefactorial (n)

if (n equals 0)

return 1

else

return (n * recursivefactorial (n-1))

end if

end recursivefactorial

 Design Recursive Algorithms:

The design methodology:

If we were to examine all hypothetically possible recursive algorithms, we would see that they all have two elements: each call either solves one part of the problem or it reduces the size of the problem.

The above example (factorial) statement 1 solves a small piece of the problem-factorial (0) is 1. Statement 2 reduces the size of the problem by recursively calling factorial with n-1.Once the solution to factorial (n-1) is known, statement2 provides a part of the solution to the general problem by returning a cake to the calling algorithm.

The statement that “solves” the problem is known as the base case. Every recursive algorithm must have base case. The rest of the algorithm is known as the genaeral case

In the example basecase is factorial (0); the general case is n x factorial(n-1).the genaral case contains the logical needs to reduce the size of the problem.

We are now ready to state the rules for designing a recursive algorithm:

• First, determine the base case
• Then determine the general case
• Combine the base case and the general cases into an algorithm.

In combining the base and the general case into an algorithm, we must pay careful attention to the logic. Each call must reduce the size of the problem and move it towards the base case. The base case, when reached, must terminate without a call to the recursive algorithm;, that is, it must execute a return.

Limitations of recursion

Recursive works best when the algorithm uses a data structure that naturally supports recursion. Trees are a naturally recursive structure and recursion works well with them. In other cases the algorithm is naturally suited to recursion. For example the binary search algorithm lends itself to a natural recursive algorithm, as does the Tower of Hanoi algorithm.

Recursive solutions may involve extensive overhead ( both time and memory)because they use calls. Each call takes time to execute. A recursive algorithm therefore generally runs more slowly than its nonrecursive implementation

Each time we make a call use up some of our memory allocation. If the recursion is deep - this is , if there are many recursive calls-we may run out of memory.

Because of the time and memory overhead, algorithms such as factorial are better developed iteratively if large numbers are involved. As a general rule, recursive algorithms should be used only when their efficiency is logarithmic.