Recursive algorithm

One of the commonly used algorithms is the recursive algorithm. Not only is it used in computer science, it can also be applied in real life.

Recursive is the process in which you divide a task into subtasks and the solution to each task depends on the smaller version of the task.

In programming, recursion is used to make a function call itself again and again until a terminating condition is met. But each time the function calls itself, the task is being divided into smaller tasks.

Application

For instance, let’s look at the factorial for a number.

Let “ n “ be a real number so.. n! Is the factorial of n.

We can say that:

n! = n*(n-1)!

We can divide it even smaller to be

n! = n*(n-1)*(n-2)!

It can be divide even further to :

n! = n*(n-1)*(n-2)*(n-3)*…..3*2*1

Here we see that we can divide n! to smaller value n*(n-1)!

We also notice that to find the answer of n! We need to find the answer to n*(n-1)! And for that we need to find the solution to (n-1)! And multiply it by n. To find the value of (n-1)! we can divide (n-1)! To a smaller value which will be (n-1)*(n-2)! To find the value of the (n-1)*(n-2)! We need to find the value of (n-2)! To find it, we need to simplify (n-2)! into a smaller value and then multiply it by (n-1) which will be (n-2)*(n-3)! This will go in until you get the value of “1” which can’t be divided into a smaller value. So, each value of the expression depends on the value before it. Since n! Depends on the value of n*(n-1)! And (n-1)! Depends on the value (n-1)*(n-2)!… etc.

The recursive algorithm contains a base condition which is the condition that terminates the operation if it is met. In the case of the factorial, the base condition is “1” because the algorithm will stop once the factorial reaches “1”.

We can write the code of the factorial in Python as follows:

The last statement “ return n*fact(n-1)” says that if the base condition is not met, then multiply “n” by fact(n-1).

fact(n-1) calls the function “fact” again but this time with the value of (n-1). The fact(n-1) says if the base condition is not met, then multiply (n-1) by and the function “fact(n-2)” . This will go on until “n” reaches 1. When n==1 it will return 1.

Once it returns 1 then it’s actually calling the function of fact (2–1) so the “1” will be the solution of fact(2–1). Originally it was:

2*fact(2–1) and we said fact(2–1) is 1 so it will substitute fact(2–1) with 1 . Now we have 2*1 =2

2*1 came from the calling of the function fact(3–1), which originally came from

3*fact(3–1), so instead of fact(3–1) we will put 3*2*1 and so on…

Towers of Hanoi

Another application on recursion is the game “towers of Hanoi”.

In this game, we have rings that are put on top of each other from the smallest to the biggest. It is required to move the rings from the tower it is in(1st tower ) to the 3rd tower. Under conditions that you can only move one ring at a time and you can’t put a big ring on top of a small ring

To reach the goal (C) we need to move the biggest piece ( red ) from A to C. To do that, we need to move every piece above the biggest piece to the middle (B) so the red ring will be able to move to C. Then we will move the rings from (B) to (C).

We divided the problem into a smaller problem that involves moving three pieces and then one piece rather than move all the four pieces at once. Now we have another problem, we need to put the green ring on top of the red ring. So we should move the the purple and the blue rings from B to A and then move the green ring from B to C. This divided the problem into a smaller problem by moving 2 rings and 1 ring rather than 3 rings at once.

Now, we need to move the purple ring from A to C. To do that , we need to move the blue ring from A to B. So

After moving the purple ring, we will move the blue ring from B to C.

That’s how we solve the tower of Hanoi using recursion.