Iteration versus Recursion

Recursion is a top–down approach of problem solving. It divides the problem into pieces or selects one key step, postponing the rest.

On the other hand, iteration is more of a bottom–up approach. It begins with what is known and from this constructs the solution step by step.

It is hard to say that the non-recursive version is better than the recursive one or vice versa. Few languages do not support writing recursive code. The non-recursive version is more efficient as the overhead of parameter passing in most compilers is heavy.

Demerits of Recursive Algorithms

Although recursive algorithms have many merits, they have their limitations. They are:

1. Many programming languages do not support recursion; hence, recursive mathematical function is to be implemented using iterative methods.

2. Even though mathematical functions can be easily implemented using recursion, it is always at the cost of additional execution time and memory space.

3. A recursive function can be called from within or outside itself, and to ensure proper functioning, it has to save the return addresses in some order so that the return to the proper location will yield the desired result when the return to a calling statement is made.

Demerits of Iterative Methods

Although the iterative method has various merits, it has its own limitations such as:

1. Iterative code is not readable and hence not easy to understand.

2. In iterative techniques, looping of statements is necessary and needs a complex logic.

3. The iterations may result in a lengthy code.

Recursive Functions

Any function written using an iterative code can be converted into a recursive code. This does not guarantee that the resulting program will be easy to understand but often, the program results in a compact and readable code.

Recursive functions are often simple and elegant, and their correctness can be easily verified.

Many mathematical functions are defined recursively, and their translation into a programming language is often easy.

If used carelessly, recursion can sometimes result in an inefficient function.

Algorithms that are by nature recursive, such as the factorial, Fibonacci, or power, can be implemented as either iterative or recursive code. However, recursive functions are generally smaller and more efficient than their looping equivalents.

Recursion is also useful when the data structure that the algorithm is to operate on is recursively defined. Examples of such data structures are linked lists and trees.

Recursion is valuable is when we use ‘divide and conquer’ and ‘backtracking’ as algorithm design paradigms.

Writing Recursive Code

The general approach to writing a recursive function is

1. Write the function header  to make sure what the function will do and how it will be called.

2. Decompose the problem into sub-problems. Identify clearly the non-recursive case of the problem (end case or base case).

3. Write recursive calls to solve those sub-problems whose form is similar to that of the original problem.

4. Write the code to combine, enhance, or modify the results of the recursive call(s).

5. Write the end condition(s) to handle any situations that are not handled properly by the recursive portion of the program.

Correctness of recursion

The following five conditions must hold true for recursion to work.

1. A recursive function must have at least one end condition and one recursive case.

2. The test for the end condition has to execute prior to the recursive call.

3. The problem must be broken down in such a way that the recursive call is closer to the base case. The base case is reached in a finite number of recursive calls.

4. The recursive call must not skip over the base case.

5. Verify that the non-recursive code of the function is operating correctly.

Recursion

In C/C++, a function calling itself is called a recursive function.

Recursion is a technique that allows us to break down a problem into one or more sub-problems that are similar in form to the original problem.

A program becomes compact and readable with recursive functions. Recursion is extremely powerful as it enables the programmer to express complex processes easily. Recursive programs are used in a variety of applications ranging from calculating the factorial of a number to playing complex games against human intelligence.

A recurrence is a well-defined mathematical function where the function being defined is applied within its own definition.

The factorial we defined as n! = n \ (n - 1)! is an example of recurrence with 1! = 1 as the end condition.

Use of stack in recursion

The stack is a special area of memory where temporary variables are stored. It acts on the LIFO principle.

The following points are to be noted when recursion is used:

1. The number of times a function calls itself is known as the recursive depth of that function.

2. Each time the function calls itself, it stores one or more variables on the stack. Since stacks hold a limited amount of memory, the functions with a high recursive depth may crash because of non-availability of memory. Such a situation is known as stack overflow.

3. Recursive functions should have a terminating (or end) condition.

4. All recursive functions go through two distinct phases. The first phase, winding, occurs when the function calls itself and pushes values onto the stack. The second phase, unwinding, occurs when the function pops values from the stack, usually after the end condition.

 Variants of Recursion

The recursive functions based on characterization are categorized as

1. Direct, 2. Indirect, 3. Linear, 4.Tree, and 5.Tail recursions.

1. Direct recursion

Recursion is when a function calls itself. Recursion is said to be direct when a function calls itself directly.

int Power(int x, int y)

{

if(y == 1)

return x;

else

return (x * Power(x, y - 1));

}

2. Indirect recursion

A function is said to be indirectly recursive if it calls another function, which in turn calls it.

int Fact(int n)

{

if(n <= 1)

return 1;

else

return (n * Dummy(n - 1));

}

void Dummy(int n)

{

Fact(n);

}

3. Linear Recursion

A recursive function is said to be linearly recursive when no pending operation involves another recursive call.

4. Tree Recursion

In a recursive function, if there is another recursive call in the set of operations to be completed after the recursion is over, this is called a tree recursion.

 5. 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 that must be stored during computation is independent of the number of recursive calls.