Recursion is a topic most beginner programmers fear and when you get the hang of it, it works like magic (Congrats! Not a noob anymore). When someone introduces recursion, they say it’s basically a function which calls back itself, and your brain goes like WHAAAAAT??
So here’s this GIF which not only gives you a complete mindfuck but also a visual description of what recursion is. Too scary huh? Well, not really. Once, you get an idea of how recursion works and which base case to work with, it runs smooth as ice. Sometimes, you won’t even be able to fathom how your code worked when it did.
Well, the mantra for recursion is ” Let recursion do the work for you”.
THE GOOD
1. For all those people who want to make their code look pretty as a picture, recursion is the best way to do that. Recursion makes a code more compact, readable and so very elegant.
2. If you can master recursion, it can turn out to be your best friend. Solutions using recursion are easier to strike and code. It also avoids redundancy of code, and your codes are easier to read and maintain.
3. Three magic words: tail call optimization: Some functional languages implement this wizardry. So basically, what happens is, if a function’s return expression is a result of a function call, the stack frame is reused instead of pushing a new stack frame in the call stack. Sadly, only a few imperative languages have this wizardry.
The secret magic of tail call
THE BAD
A lot of programmers avoid using recursion and believe that it is less efficient than it’s iterative counterparts.
1. Recursion can lead to the perils of stack overflow. To understand better, let’s look at the steps for functions call:-
- space is carved out on the stack for function arguments and variables.
- arguments are copied into this new space
- control jumps to the function
- function code runs
- function results are copied into the new value
- stack rewounds to its previous position
- control jumps back to the caller
Mostly, all of these steps consume more time than their iterative counterparts. Therefore, recursive methods are relatively less efficient in those cases.
2. More importantly, when most programs start, they allocate a single chunk of memory to the stack, if that memory is used, the entire program crashes due to stack overflow.
3. Each function call eats up a lot of space. That amount of space isn’t recovered until the function returns. Iterative methods do not suffer from such problems.
