by Cyber Cat
3.7 .. 29 reviews
1980 Views
The Beautiful Concept of Recursion

Chapter 1 of 7

Introduction
Recursion is a very interesting concept from the field of computer science. While the definition of the concept is quite simple, its applications have kept most of the computer science community who are new to it, confused and frustrated. For this reason it has also become the subject of many witty jokes over time.

In this guide we'll try to understand 'Recursion' as simply as possible (at least so that we can make sense of some of the witty jokes). Even if you're not from the field of computer science or an academic, it might be a fun ride knowing about the idea of 'Recursion'. 

Chapter 2 of 7

The Journey
Let's begin with a simple situation. We are on a bicycle and want to journey from point A to point B, 10 miles away. There are two ways we can think of achieving this.

The Iterative Way

Our first plan is to cover the distance 1 mile at a time. So we break our journey into small steps of 1 mile each. Each step begins and ends completely before the next step begins.

What do we do at each step?
As per plan each step will include two actions.
Action-1 will be cycling for 1 mile.
Action-2 will be reducing the count of remaining miles by 1. Counting the remaining miles tells us if we need to perform one more step. 
This way we complete Step1. At the end of Step1 our count tells us that we need to do another step. So then we do Step2 and so on until we reach Step 10. At Step 10 our count becomes zero and we stop. Each step is independent from the other steps and complete on its own.

The Recursive Way

Let's call our journey of 10 miles (from A to B) as JOURNEY(10)

So what actions do we perform to complete JOURNEY(10)?
Action-1 will be cycling for 1 mile. 
Action-2 will be going on a journey of remaining 9 miles

So basically, going on a JOURNEY(d miles) means cycling for 1 mile and then going on a JOURNEY(d-1 miles). This implies that this step of going on a JOURNEY(d) will not be complete until you finish the step JOURNEY(d-1)

Each step is made up of a smaller step of the same type. The completion of each parent step relies on the completion of the child step. At one point you will arrive at a child step that has a simple result and doesn't require any further child steps.

So to complete JOURNEY (10), you need to complete JOURNEY(9), for which you need to complete JOURNEY(8) and so on, until you are required to complete JOURNEY(0). And you know that JOURNEY(0) doesn't require you to do anything as you have reached your destination. So you stop there.

This completes JOURNEY(0), which in turn completes JOURNEY (1), and now going upwards . . . which in turn completes JOURNEY(9), which completes JOURNEY(10).  Check out the picture below, it might help you grasp this better.

Chapter 3 of 7

Recursion - A Formal Look
We just saw how recursion works through an example. So now let us take a more formal look at the concept.
A function whose definition includes making a call to itself, is called a recursive function.
As you can see, the definition of a function named 'Calculate' is given above. The definition includes a set of commands that must be executed when the function is called. What you can also see is that one of those commands is the function itself. Thus Calculate will be called a recursive function and the process of executing it would be called recursion. 

Chapter 4 of 7

But Won't It Go On Forever?
Well on the first look it seems that a recursive function would keep on executing forever, because each function call begins another function call inside it thus creating a never-ending chain. 
That's correct, a recursive function would keep on executing forever, if we don't attempt to stop the chain. To stop the recursion chain, we specify a 'Base Case'. 

Going back to our JOURNEY example, let us consider that our journey of 'd miles' is represented by a function JOURNEY(d). Remember, how we started with the case where d=10 miles. The distance d kept reducing with every new recursive call of the JOURNEY function finally arriving at a case where d=0
It was quite evident that we did not require calling the JOURNEY function again to find the answer to JOURNEY(0). 

JOURNEY(0) was simply 0. This case of d=0 was simple and evident enough with a known answer, that we could just stop the recursion chain there. This was the base case for the JOURNEY function.

Thus a Base Case is a case in the execution of a recursive function, where the answer of the function call does not require any more recursive calls, but instead the answer is already known or very simple to calculate.

Specifying The Base Case Is A Must

To protect the recursive function from executing infinitely, we must specify the base case that will stop the recursion. There may be more than one base cases.
The base case is written inside the definition of the function, specifying clearly that when the base case is reached a known answer should be returned & the recursive function call (which is also a part of the definition) should be bypassed. 
When defining the function in code format, an 'if-statement' is usually used to decide whether the base case has been reached in the recursion chain.

Chapter 5 of 7

The Jokes :D
Remember about 'Recursion' being the  subject of some witty jokes. The most popular one is given below.
And here's another one.
Hope you were able to understand the recursiveness of the situations and got a good chuckle out of it. 

Chapter 6 of 7

How Can Recursion Be Helpful?
The biggest advantage that recursion brings with it, is that recursive functions make lengthy iterative programs small and succinct. Iterative programs that would otherwise take lengthy complicated loops and flows, may sometimes be expressed much easily using recursive functions.
And that's the whole point. 
When given a problem to solve, can we find a recursive approach to solve the problem because it would be simpler to code.
That is, can we represent the problem as a recursive function which involves a smaller version of the same problem. 


For example - Find The Factorial of A Number

For those who might not be familiar with the term, 'factorial' of a natural number 'n' is the multiplication of all natural numbers starting from 1 up to that number n.
factorial( n ) = 1 * 2 * 3 * 4 * 5 . . . * n

Iterative Approach:
If we were using our normal iterative approach to calculate the factorial of any number, we would write it like below.
Recursive Approach:
If we look closely, its easy to see that factorial of a number n is just n multiplied to the factorial of the number 1 less than n.

factorial(5) = 1 * 2 * 3 * 4 * 5
factorial(4) = 1 * 2 * 3 * 4
factorial(5) = factorial(4) * 5       or    5 * factorial(4)
Thus, factorial(n) = n * factorial(n-1)

We have just reduced our factorial problem into a smaller version of the same problem. We can then write it as a recursive function in code (javascript here) as given below.

Chapter 7 of 7

The End
This was a basic introduction to the concept of recursion. It is a powerful approach to solving algorithmic problems in computer science, and also quite elegant (in the sense that simpler code is more beautiful). 

While finding how to convert a problem into a smaller version of the same problem is the biggest challenge, other issues like limitations in computer memory only add to it. 


If you really enjoyed reading this guidebook share it with other friends who could be interested in it too and also leave a rating as a feedback.

Rate this guide
(Doesn't require signup)
Submit

Continue Reading ...

229 Views
162 Views