Recursion is the process of determining something in terms of itself. To have a better understanding of recursive functions, here a trainer from the Python Institute in Delhi is going to make you learn about how Recursion works in Python programming and how we can use it to solve real-world problems. This topic might seem tricky at first sight but after going through this blog post, you will have better clarity about the subject.
So, to understand this we are considering a real-life example. We want to fill a bucket of water and my function is fetching only a “cup of water” at a time. We will keep repeating the process again and again until my bucket is full which will be my base condition.
In the same way, Recursions are functions, but when inside a function you call the same function, it’s called recursion.
We can run a function, inside a function. For example: We made a function for ‘average’ and want to use the function of ‘sum’ inside it. We definitely can do that.
How Recursion in python works exactly?
Well, recursion is a process in which a function repeatedly calls itself either directly or indirectly. Those calls are made mainly by explicitly calling the function by its name. However, it can also be done by implicit calling as well. The core logic behind the repeated calling of the main function again and again inside itself is to break a larger and more complex problem into smaller sub-parts. We do this to reduce the computational complexity of a larger problem by breaking it into pieces. Breaking a problem into sub-parts is known as the “divide and conquer” approach in programming.
Let us discuss the general structure of the recursive function:
Function Definition: We are taking an example to give factorial. The function “factorial” takes an integer “n” as an argument.
def factorial(n):Normal Case: This is the condition where a function stops calling itself or terminates. FOR EXAMPLE: If n becomes 0, it will return 1.
if n==0:
return 1Recursive Case: This is the condition where the function keeps calling itself. FOR EXAMPLE: Here, to get the value of factorial we will call the same function but with a different parameter this time i.e. factorial (n-1).
else:
return n*factorial(n-1)If n is not 0, the function calls itself with (n-1) and multiplies the result by n. If you have defined a recursive function, where you only have a recursive case but you do not have a base case that means the function will never going to terminate by itself. This will result in infinite recursion and can crash your application.
NOTE: When you create a recursive function, it’s important to include a base case so that the function knows when to stop calling itself.
Types Of Recursion in Python
Direct recursion
Here, a function directly calls itself. Above, we have already discussed an example while calculating the factorial of a number.
Indirect Recursion
In indirect recursion, a function calls another function which will further call the original function again.
Tail Recursion
Tail recursion is when a recursive call happens at the end of the method after other processing.
Here ‘n’ is the number of which we want to calculate the factorial and accumulator (which accumulates the results, having default value 1) are the two parameters taken by the above-defined function.
When n is 0, the function returns the value of the accumulator (base case). If n is greater than 0, the function will make a recursive call to itself with parameters (n-1) and (n*accumulator) until n becomes 0.
Head recursion in python
Head recursion is when a recursive call happens at the beginning of the method before other processing.
If “n” will be less than 1, the function stops the recursion.
Output
Tree recursion
A recursive function that calls itself more than one time is referred to as tree recursion.Let us try generating Fibonacci numbers as an example of tree recursion.
We have defined the function as Fibonacci (n). If the value of n becomes 0 or 1, the function will directly return ‘n’ which is the value of base cases. The first two numbers of the Fibonacci series are 0 and 1. If in case n>1, the function will call itself recursively with two different parameters i.e. (n – 1) and (n – 2), then their results will be added. The function will Recursively call itself until the value of n reaches the base cases.
If you are still confused about data structures, here is our data structure course
Nested Recursion
In nested recursion, a recursive function will pass a parameter as a recursive call.Here, we are writing a pseudo code to make you all understand.
Number (n-1) is a parameter but itself is a recursive call which truly means, that unless the result of the recursive call [Number (n-1)] is obtained, this call [return number ()] cannot be made.So, a recursive call is taking a recursive call as a parameter. This is recursion inside recursion. Hence, it is called nested recursion.
Recursion is the fundamental technique of Computer Science, which can be applied to solve many types of problems in different domains.
Use Of Recursion In Python for Mathematical Computation:
Recursion is used in the mathematical calculation due to its simplicity. We can use recursion to find out the factorial of any number, print the Fibonacci series, finding the greatest common divisor of 2 numbers, exponentiation and many more. Now let’s say, we talk about factorials in case. We will take the example of factorial 7 which means 7x6x5x4x3x2x1. Whatever value you get after multiplying these is the value for 7!
If we talk about factorial 6, we’ll multiply from 6 to 1, and we’ll get the value of the factorial 6. Similarly, we can find the factorial of any number we want. By definition, the factorial of 0 is 1.
- 7! = 7*6*5*4*3*2*1 à 7*(7-1)!
- 6! = 6*5*4*3*2*1à6(6-1)!
- 5! = 5*4*3*2*1 à5*(5-1)!
- 4! = 4*3*2*1à4*(4-1)!
- 3! = 3*2*1 à3*(3-1)!
- 2! = 2*1 à2*(2-1)!
- 1! = 1
By the logic defined above we can conclude that, if we need the factorial for any number, first we’ll find the factorial of the (n-1) and then multiply it by ‘n’. We will use this information to recursively calculate factorials. Firstly, we will write it down in the form of a Python program.
Firstly we have defined our function as factorial (n).Here, the base case is ‘n=1 and 0’. For 0 or 1, the value of the factorial will be 1. Other than that, the else statement will be executed i.e. n*factorial (n-1).We have called the same function inside a function.
For the Fibonacci series, we have already discussed the code in the above examples.
Use Of Recursion In Data Structures
We will understand how recursion is used and implemented within the three methods. Let’s start by briefly talking about the nature of trees and why recursive logic always seems to be the way to go when trees come up.
These trees are made of sub-trees and those sub-trees are further made up of other sub-trees and ultimately all of these sub-trees are the same tree.
Eventually, we reach a point, where the sub-trees are just the nodes and each node can be considered a tree itself. Because to traverse a tree all you need is one node and using this single node you can go ahead and visit all the nodes belonging to that tree.
This is actually why a lot of people perceive trees as recursive data structures. Remember how we defined recursion as solving sub-problems of a bigger problem?
The tree also applies to the specific elements or the nodes and by traversing these nodes one by one we are aiming to reach a bigger target. With this in mind, let us take the “in-order traverse operation” as an example and try to implement it for the tree.
To traverse a single node in an “in-order manner” we will traverse in the order below.
- Visit the left child
- Visit the actual node
- Visit the right child
For the sake of this example, we’ll simply be printing out the values stored inside the node. Here, we have one common example of the traversal of binary search trees.
Defining the structure of a node in a binary tree:
In-order traversal function:
Creating the binary tree:
The binary tree will be created this way:
The nodes will be traversed in the order à left sub-tree, root, and right sub-tree. The “in-order traversal” of this tree structure will result in the following sequence:
Initially, the function is called with the root node having value 1. Then, it will recursively call itself to traverse the left sub-tree (root. Left). This process will continue until the entire tree is traversed.
This is not the only case where we can use recursion while working with data structures but in binary trees as well, we can traverse nodes in different orders such as in-order, pre-order, and post-order traversal.
Solving puzzles using recursion
As a practical example of recursion, we are discussing the tower of Hanoi problem. As you can see, in this problem we have three poles and in one of the towers we have some discs. Here, we have three discs in it. We will generalize this mathematical puzzle with three rods and ‘n’ number of discs.
The objective of this puzzle is to move the entire stack to another rod i.e. target pole.
We have to transfer all three discs to the destination tower or the end tower. For transferring them to the last tower, we can take the help of the middle tower or the auxiliary tower. But the task of transferring discs to particularly last tower is not that easy because here is where the rules of the games apply. Moving off disk should follow the following rules.
- Only one disk can be moved at a time.
- A disk can only be moved if it is the uppermost disk on the stack.
- No disk may be placed on the top of a smaller disk.
Here are the suggested steps:
- The first move is to place the upper disc on the last pole.
- Then, transfer the middle disc to the auxiliary node.
- Put the disc in the last pole to the auxiliary pole.
- Place the lowest disc of the first pole in the target pole.
- Place the upper disc of the auxiliary pole on the first pole.
- Disc in the helper node will be transferred to the targeted pole.
- The leftover disc in the first pole will be transferred to the last pole as a final move.
These are the minimum 7 moves to solve this problem. Now, we will see the coding part of this problem making use of recursion.
We want to solve the problem for the (n-1) disk. We all know that recursion is calling a function itself again and again for a lesser size of input until the base conditions.
Every time we will transfer the (n-1) disk to the pole to get the desired output.
Advantages of recursion in python
The code is clean and elegant in our recursive function and the composite task can be broken down into simpler sub-programs using recursion in python. That is one biggest advantages of using it.
You can generate sequences more easily with the recursion than using some nested iteration.
Disadvantages of using recursion in Python
If we follow the logic behind the recursive function, it might be hard sometimes. Recursive calls are quite expensive and inefficient as they take up a lot of memory and time. Using recursive functions is pretty hard to debug as well.
All the examples explained above, show us that besides coding for some examination purposes, recursion is a function which we use to solve real-world problems by breaking them into pieces. This is a powerful tool in the world of data structures and algorithms. Still, if you guys have some doubts, you can reach out to our mentors at python training institute in Delhi or join our online python course