Advantages and Disadvantages of Recursion (Recursive Algorithm)

A procedure or subroutine is recursive if it calls itself, and this process is known as recursion. Commonly, a non-recursive solution to a programming problem is more efficient in both runtime and memory space basis than a recursive one. It is due to the need of making multiple function calls. The function is called each time of the recursive step until the stopping condition is satisfied. Also, every time it goes through a recursive step, it has to store the return addresses and copies of local variables, all of which makes it consume a lot of time as well as memory.

Another fact we need to consider is that if the number of recursive steps is very large, we can actually run out of memory space causing the memory stack overflow, and the program to crash. Say if we want to recursively display the Fibonacci series up to 2000^th number, the program would have to handle 2000 return addresses, and a lots of local variables, which is very inefficient than a simple iteration using a for-loop.

However, recursive functions are relatively shorter, and hence easier to write and debug. For some complex problems, they could present a very easy and straightforward solution, like Binary Search and Quick Sort. Basically, if recursive algorithm is not much shorter than the non-recursive one, we should always go for the non-recursive one. A well written iteration can be far more effective and efficient in such cases.

Reference:

Heathcote, P. M. (2000), Recursion, ‘A’ Level Computing (pp. 235- 237), Ipswich, UK: Payne-Gallway Publishers