There are more than one types of recursion which we are going to learn in this blog. Recursion is defined as a process of calling a function or method again and again to execute a specific task. We use recursion in programming to solve a number of problems such as backtracking, tree traversals, tower of hanoi, sorting, and more.
In this article, we are going to get an overview of the Recursive function and their uses in programming. We will also learn the many different types of recursion in the programming language.
What is Recursion?
Recursion is an important method in solving logical problems through divide and rule methods. It breaks a complex problem into simpler subproblems which can be solved with logic easily. A Recursive function involves calling a function again and again until it reaches a base condition and stops.
It is very much important to provide a base condition for a function execution otherwise the recursion call will keep on happening infinitely. In this article, let us know more about Recursion and their types in programming languages.
What is a Recursive Function?
A Recursive function is used to hold the logic of the complete recursion to execute a specific task. Recursive function consists of two important stages i,e. A base condition and a recursive logic. Let us understand the common structure of a recursive function below.
| void recurisve_function( parameter)
{ if (base condition){ // statement } return recursive logic; } |
As you can see the complete recursive function is divided into two parts i,e. Base condition and recursive logic. It is very much important to clearly define these two parts to get the accurate solution of your problem through recursion.
- Base condition: It is a stopping condition used in a recursive function that can be used to stop a function after a number of executions.
- Recursive logic: This is a logic which is used to run the recursive function for a definite number of times again and again.
A Recursive Function Example
Recursion is repeated calling of a function repeatedly for a definite number of times. Let us understand recursion with a suitable example of factorial function.
| def factorial(n):
if n == 0 or n == 1: # Base case return 1 else: return n * factorial(n – 1) # Recursive case print(factorial(6)) |
You can see the base condition and recursive function logic defined inside a recursive function. The base condition runs when the value of the number comes to 0 or 1 which will return a value of 1. We will also use a recursive function n*factorial(n-1) which will keep on repeating the function again and again.
Types of Recursion in Programming
There are two major classifications of a recursion in programming where one function keeps calling itself which is known as direct recursion. But if one function calls another function mutually then it is called an indirect recursion function in programming.
1. Direct Recursion
The direct recursion as we discussed above is a function which keeps calling itself again and again until a base condition is reached. It further divides types of recursion in following given parts.
- Head Recursion
- Tail Recursion
- Tree Recursion
- Nested Recursion
A. Head Recursion
If the recursive function call in a recursion is made in the first statement then it is defined as head recursion. There is no code execution or statement before the recursive function call; everything comes after the recursive call in the function.
All operations are done at the returning time and are free to move ahead without processing any operation while calling the function. Let us understand this type of recursion with the help of an example below.
| def head_recursion(n):
if n == 0: return 1 result = head_recursion(n – 1) #Head Recursion return n * result print(head_recursion(5)) |
B. Tail Recursion
This type of recursion makes the recursive call at the end of the function which means there will be no pending expression or operation after the recursive call in the function. Let us understand this type of function with the help of an example below.
| def tail_recursion(n, accumulator=1):
if n == 0: return accumulator return tail_recursion(n – 1, n * accumulator) print(tail_recursion(5)) # Output: 120 |
As you can see the recursive call in this type of recursion is done at the end and no expression or logic comes after that. The function passes the result in the accumulator.
C. Tree Recursion
In Tree recursion a function will call itself multiple times in a single execution which forms a tree-like structure of recursive calls. We can understand this theory with the help of a simple example of Fibonacci Sequence.
| def tree_recursion(n):
if n <= 1: return n return tree_recursion(n – 1) + tree_recursion(n – 2) print(tree_recursion(5)) |
D. Nested Recursion
In this type of recursion, we will observe “recursion within recursion” i,e. A recursive function will pass the parameter in the recursive call. The recursive function argument itself contains a recursive call.
| def nested_recursion(n):
if n > 100: return n – 10 return nested_recursion(nested_recursion(n + 11)) print(nested_recursion(95)) # Output: 91 |
2. Indirect Recursion
These types of recursion contain indirect calls to more than one function. There are more than one functions calling one another in a circular manner in an indirect recursion. We will understand these types of recursion with the help of an example. Let us print numbers starting from n down to 1 and back to n using indirect recursion.
| def functionA(n):
if n > 0: print(n, end=” “) # Print before calling functionB functionB(n – 1) # Call functionB def functionB(n): if n > 0: functionA(n – 1) # Call functionA print(n, end=” “) # Print after calling functionA # Call the first function functionA(4) #output 4 3 2 1 1 2 3 4 |
Let us analyse the flow of the function call in these types of recursive function calls.
| functionA(4) → functionB(3) → functionA(2) → functionB(1) →
functionA(0) (Stops) ← functionB(1) (prints 1) ← functionA(2) (prints 2) ← functionB(3) (prints 3) ← functionA(4) (prints 4) |
Upskill with PW Skills Online Learning Programs
Enroll in PW Skills online Learning programs to upskill your knowledge and understanding of programming and data structures. Learn how to write a recursion program and make it more effective and optimised.
Join any of the programming courses and learn from dedicated mentors in our online learning program. Become a certified web developer, programmer, designer and more with pwskills.com
Types of Recursion FAQs
Q1. What is a Recursion Function?
Ans: Recursion is an important method in solving logical problems through divide and rule methods. It breaks a complex problem into simpler subproblems which can be solved with logic easily.
Q2. What are different types of recursive functions?
Ans: There are different types of recursion in programming, let us know about some of the major classification.
Direct Recursion
Indirect Recursion
Head Recursion
Tail Recursion
Nested Recursion
Tree Recursion
Q3. What is a direct recursion?
Ans: The direct recursion as we discussed above is a function which keeps calling itself again and again until a base condition is reached.
Q4. What is indirect recursion?
Ans: These types of recursion contain indirect calls to more than one function. There are more than one functions calling one another in a circular manner in an indirect recursion.
