In previous posts, I’ve explained how to write C++ program to find factorial with recursion and with iteration. Also there are 2 other posts to generate Fibonacci series with recursion and with iteration. Now we’ll compare Recursion and iteration. Theoretically, everything that can be implemented using iteration can be converted to corresponding recursive implementation. Here we will compare which implementation is better in terms of expressibility, readability, writability, maintainability, performance and memory.
Basically recursion is the process by which a function calls itself. This helps us to express the logic in terms of themselves. For example, to find factorial of a number, we have the mathematical equation:
Factorial of n = n * factorial of (n-1)
When we write the program to find factorial using recursion, we convert the same mathematical equation in to a function, i.e., a function which returns the product of n and factorial of n-1. Thus recursive function is more expressible in case of mathematical equations and some other cases like building a binary tree etc.
In many cases, a recursive function is easier to read and understand than the one written using iteration because they are straight forward. But in few cases, complex recursive functions may be difficult to understand than iterative function, just for kidding, the reason behind this may be we need to create additional stack traces in our brain too, to guess the output of a recursive function!
One of the main advantages of recursive function over iteration is, in most cases, recursive implementation needs less lines of code and fewer variables. Thus in terms of writability, recursion is better in almost all cases.
In terms of maintainability too, recursion ranks more. Recursive functions are easier to maintain than the one written using iterative function.
In terms of performance, iteration ranks far more than recursion. Recursive programs perform slower than iterative function. The main reason behind this is that it needs more function calls and needs to create additional stack traces in memory.
But recursive program performs far better, if your recursive function is well written with performance in mind and if your compiler is smart enough to optimize tail calls.
In normal cases, recursive function uses lot more memory than iterative function. This is because it needs additional stack traces in memory for each function calls.
As in case of performance, memory usage of can also be reduced, if your compiler can optimize tail calls and you program is well written.
It is up to the situation, whether to implement recursion or iteration. If performance and memory is your number one, use iteration. In most other cases, you may prefer recursion. Also recursion doesn’t make sense in few cases, where iteration should be preferred. In short, although recursion has less performance and more memory usage, it can be made up by its readability, expressibility and maintainability. So it is up to you to choose which to implement, and I think now you are mature enough to choose which one suite your situation.