Recursion

• Recursive procedures are the easiest at first it may appear that recursive procedures are time consuming, but it is not so if we include the total time of design, implementation, and testing.
• A recursive procedure uses itself (that is, calls itself). Usually we a recursive definition of an itself is best expressed in a recursive way, that is, by some form of recurrence relation.
• A famous example is the factorial function, which is defined by the recurrence
• relation, defined for n > 0:

Factorial Algorithm
function FACT(n)
if n = 1 then
   return 1;
else
   return n * FACT(n - 1);
end

• This is implemented as an algorithm of the function in a pseudo-code as follows:

Algorithm 
function FACT(n)
Step-1: [calculates factorial function of a positive integer by recursion]
Step-2: if n = 1 then
Step-3: fact = 1;
Step-4: else
Step-5: fact = n * fact(n - 1);
Step-6: end

• There is a one-to-one correspondence between the definition of the recursive function and its algorithm.
• This is the reason why recursive algorithms are used, even though they may be inefficient in terms of memory space and time for execution.
• A direct translation of our conceptual understanding to an algorithm is possible.

Order Of Execution Of Statements In A Recursive Function 

• While developing, analyzing, and debugging a recursive function, it is necessary to be aware of the order in which various statements are executed in the function. We shall represent the recursive function as a skeleton only. Suppose the general recursive function is represented as f(x){S1; if x = base then return b else f(x -1); S2;} 
• Here f(x) is the recursive function with input argument x, S1 is the group of statements before the test for recursion (may be null), S2 is the group of statements after the recursion (may be null), b is the base value returned for f(x) if x is equal to the base (that is, the stopping condition) and f (x - 1) represents the function at one level lower than f(x). The order of execution is: S1(x), S1(x - 1), ... S1(base), S2(base + 1), ... , S2(x - 1), S2(x)