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
Thank you.

ReplyDeletegreat article on recursion

ReplyDelete