Recursion

What is Recursion?

Definition: Recursion is a process in which a function calls itself as a subroutine.

The function itself that use the process of recursion is called a recursive function.

Anatomy of a recursive function

A recursive function always has a termination condition that’s almost always implemented with an if-else statement. Think of it in this way:

if(last step of recursion?){
do final steps.. ;
}
else{
proceed with recursion again.. ;
}

Why do we need a recursion? I thought we had loops?

Loops instruct a computer to repeat certain instructions until a condition is met while recursion keeps calling itself until a certain condition is met. If you think carefully, almost every recursive problem can be solved using a loop but every loop can’t be solved using recursion.

There is an interesting fact I came across. Recursion came into existence after loops were already known about somewhere in the 1940s[1].

There are some problems you can set in computing that you cannot decide by any algorithm at all. Not my words but Alan Turing’s in his paper “ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM” in 1936. A certain set of those problems are intrinsically recursive. The problem with not having a clear idea of what the termination condition would be.

One such example would be the Ackermann’s function

For problems like these, we really need recursion although we have loops. At other times, it’s just easier and quicker to use a recursive function instead of loops. It also makes understanding code a lot easier but that depends on who you ask.

References:

Author: Victor Fernandes

A friend I really respect once told me, unless you are able to dumb down a concept for someone who has no prior information about it, you can't be sure you know it yourself. I try to create blog posts that are extremely easy to understand most suitable for those in a hurry. The topics I write about include web development, digital marketing and software in general.

 
Notice an error in any content or would like to get something removed? Please inform Victor here.

Leave a Reply

Your email address will not be published. Required fields are marked *