Recursion Versus Iteration

RECURSION VERSUS ITERATION

Recursion is more of a top-down approach to problem solving in which the original problem is divided into smaller sub-problems. On the contrary, iteration follows a bottom-up approach that begins with what is known and then constructing the solution step by step.

Recursion is an excellent way of solving complex problems especially when the problem can be defined in recursive terms. For such problems, a recursive code can be written and modified in a much simpler and clearer manner.

However, recursive solutions are not always the best solutions. In some cases, recursive programs may require substantial amount of run-time overhead. Therefore, when implementing a recursive solution, there is a trade- off involved between the time spent in constructing and maintaining the program and the cost incurred in running- time and memory space required for the execution of the program.

Whenever a recursive function is called, some amount of overhead in the form of a run time stack is always involved. Before jumping to the function with a smaller parameter, the original parameters, the local variables, and the return address of the calling function are all stored on the system stack. Therefore, while using recursion a lot of time is needed to first push all the information on the stack when the function is called and then time is again involved in retrieving the information stored on the stack once the control passes back to the calling function.

To conclude, one must use recursion only to find solution to a problem for which no obvious iterative solution is known. To summarize the concept of recursion, let us briefly discuss the pros and cons of recursion.

The advantages of using a recursive program include the following:

• Recursive solutions often tend to be shorter and simpler than non-recursive ones.

• Code is clearer and easier to use.

• Recursion works similar to the original formula to solve a problem.

• Recursion follows a divide and conquer technique to solve problems.

• In some (limited) instances, recursion may be more efficient.

The drawbacks/disadvantages of using a recursive program include the following:

• For some programmers and readers, recursion is a difficult concept.

• Recursion is implemented using system stack. If the stack space on the system is limited, recursion to a deeper level will be difficult to implement.

• Aborting a recursive process in midstream can be a very slow process.

• Using a recursive function takes more memory and time to execute as compared to its non-recursive counterpart.

• It is difficult to find bugs, particularly while using global variables.

The advantages of recursion pays off for the extra overhead involved in terms of time and space required.