Essential Recursion Programs in Python

Recursion is one of an important concept of programming to solve problems. Every beginner encounters with the recursion even the experience developers’ use recursion. If you are not familiar with recursion, it is function that is called itself. For example – Place two parallel mirrors facing each other, if any object appear in between them, it would reflected recursively. To learn more about recursion, follow www.javatpoint.com/recursion-in-python.

In this tutorial, we will solve some important Python problem using recursion. It will help to make the good understanding of recursion and how to take approach to solve problems.

Let’s see these problems as following.

Find of a Number

It is an introductory or famous problem of recursion. The factorial of a number is calculated by multiply number itself and n-1 until we get one. Suppose we want to want factorial of 5, then it will goes as below.

As we can see that, it is calculating n*(n-1) repeatedly. Hence we can use recursion. Here the factorial of 0 is 1. The recursion’s base case as below –

The code will be as below.

Example –

Output:

Enter a number: 6
The factorial of a 6 is:  720

Fibonacci Sequence

It is a most famous mathematical problem and sometime also asked in interview at entry level jobs. In this sequence, each number in the sequence is the sum of the two numbers that precede it. The series will be 0, 1, 1, 2, 3, 5, 8,.…so on. The first element is 0 and second is 1; hence the third element is sum of first and third element. Suppose we want 6^th element of Fibonacci series, the preceding two elements will be 5 and 4 –

The sequence Fn is defined by the recurrence relation as below.

With the seed values –

Let’s implement the recurrence relation using the Python code.

Example –

Output:

Enter a number: 7
The 7 element of fibonacci series is:  13

Sum of the First n Natural Numbers

It is simple problem, where we find the sum of the n natural number using recursion.

Example –

Output:

Enter a number: 6
21

Power of Number

To find a power of number, there is a Base number and an Exponent. The product of multiplying a number by itself the same number of times as the exponent’s value. The exponent is written above and to the right of the base number. It is decreased every time when the base number is multiplied.

Example –

Output:

4 to the power of 7 is: 2187 
2 to the power of 8 is: 64

Least Common Multiple (LCM) of 2 Numbers

In the mathematics, LCM is a smallest common factor of the two or more numbers. For example – We want to find the common factor of 2 and 5 then –

Multiples of 2 → 2, 4, 6, 8, 10

Multiples of 5 → 5, 10, 15, 20, 25

Least Common Factor is → 10

Let’s see the following example –

Example –

Output:

The least common factor is:  16.0

Greatest Common Divisor (GCD) of 2 Numbers

It is also known as Highest Common Factor (HCF), it is a highest common factor that divides both the given numbers. For example – Suppose we want to find the HCF of a = 98, and b = 56.

Here a>b so we change the value of a by subtracting by b, and b remain same

a = a – b =98 – 56 = 42 and b = 56. Now b>a so b = b – a = 56 – 42 = 14 and a = 42. 42 is 3 times of 14 so HCF is 14.

Let’s implement it using the Python code.

Example –

Output:

GCD of 24 and 48 is 24

Tower of Hanoi

It is a famous mathematical puzzle where three rods have three disks. The main task is to move the entire stack to another rod that should follow the given rules –

• Only one disk can be moved at a time.
• The most upper disk from one of the rod can be stimulated in move.
• The smaller disk cannot be placed at the lower of the largest disk

Let’s solve the code using the following example.

Example –

Output:

Enter number of disks: 2  
Move disk 1 from rod A to rod B.  
Move disk 2 from rod A to rod C.  
Move disk 1 from rod B to rod C.  

Sum of Digits of a Number

We can also use the recursion to solve such problems. Suppose the user enters 143, the sum of the digits will be 1+4+3 = 8. Let’s understand the following example.

Example –

Output:

Enter a number: 143
The sum is: 8

Merge Sort

The merge sort algorithm works of the Divide and conquers and it is a most efficient algorithm. In a merge sort algorithm, the given array breaks down in several arrays until each array consists of a single element. After that, the sorting is performed and merged into the single array. Visit our merge sort algorithm in Python to get the detailed explanations.

Example –

Output:

Input Array: 
[24, 11, 50, 27, 16, 36, 60, 91]
Sorted Array :
[11, 16, 24, 27, 36, 50, 60, 91]

Pascals Triangle

Pascals triangle is a different kind of triangle where each number is the sum of the above two apart from the edges, which are all ‘1’.

Let’s understand the following code.

Example –

Output:

Enter a number: 6
[1, 5, 10, 10, 5, 1]

Conclusion

Recursion allows us to reduce the number of lines from the code but it uses more memory. In this tutorial, we have discussed some simple problem that can be solved using recursion. These common problems can be asked in the programming interviews.