What Recursion? Why Recursion?

“If you want to know what Recursion is, see Recursion”

I have been writing code in C and C++ since my first year of college. I remember our Professor just took one class on recursion saying “Recursion is a function calling itself” gave a few examples like factorial of a number, fibonacci series and left.

I have always been amazed with Recursion, it is just so amazing, and my hate for “For loops” is something I’m not proud of. Except for writing algorithms for solving competitive programming problems I’ve not seen many people, especially “Developers” who actually use it, they just use “for loops” or “mapping” for literally everything. I have been a developer myself, and I write code in React and NodeJS on a daily basis now. Wherever I can I use recursion instead of loops, they just make more sense.

Writing a recursive function takes hardly more than 5-6 lines of code, most of the work that you have to do is just thinking. Thinking in recursion is more like how a computer would think. Ok, you might think a very long recursion would fill up your stack memory, and so many repetitive calls would be made. Yeah, you might be right, but there is a real easy way to solve this, use memoization, just store the result of every call you have made, and check if that same call is made again, just use the stored result. Ok what about memory? Too many calls, would fill up the stack right? Maybe, but we already have a solution for that, something the cool kids call “Dynamic Programming” or lets say “The top-down approach”. 

I know, I know , I know.

TDA is iterative I know, like I said I hate for loops, or loops in general, then why am I talking about TDA? See DP is enhanced recursion or just Recursion with Memoization. I have solved a lot of problems in recursion.

There are a few things I have noticed. Remember “functions” from class 11-12th mathematics?  

Something like f(x) = f(x-1) + x

That rings a bell right? This is recursion in mathematics, the time when we didn’t have computers mathematicians used recursion, they didn’t call it recursion but it was actually what we use in computer science nowadays.

f(x) = f(x-1) + x 

Doesn’t this look familiar? Ok let me put it this way

int f(int x){

if(x==0){

return 0;

}

return f(x-1) + x;

}

Isn’t the output of this function the sum of first x natural numbers?

Yes, recursion is as old as mathematics itself.

You must have heard of the Josephus problem?

How a soldier got trapped with 40 other soldiers in a cave while they were surrounded by an enemy army. They wanted to be dead instead of being captured by enemy army so they decided to stand in a circle and kill a soldier next to them, one by one, till one soldier stands and he has to commit suicide at last. But Josephus didn’t want to get killed. And at last he was the one standing and he surrendered himself to the enemies. So how did he know which place to stand in the circle? Later it was found he was a mathematician, he knew recursion.

Recursion saved his life, Not for loops I guess.