We have already talked about recursive functions many times in different programming languages and solved popular problem statements using the recursive approach. But do we know how to create recursive functions, its important ingredients, methods and more? Recursive functions are expressions enclosed within a single block used to execute a specific task by repeating itself again and again.
This function is frequently used in programming languages like Python, C++, Java, PHP, or more. Let us understand how we can frame recursive functions easily along with some solved examples.
What are Recursive Functions?
As we are already familiar with what recursion is, we will now know recursive functions. Recursion functions are a set of expressions enclosed within a curly brackets which contains repeated logic expressions calling itself again and again and a base condition which is used to stop the function calls.
Let us understand the structuring of a recursive function below.
Structure of Recursive Functions
Recursive function can be used to create a well structured and confined set of programming expressions used to execute a certain specific task, such as factorial function, fibonacci series, tower of hanoi. All of these problems can be achieved using recursive functions.
| def recursive_function (parameter)
{ if (base condition) { //code } recursive calls return results } |
1. Base Case (Termination Condition)
In this stage we define the condition which will be used to stop the recursion calls. Without a base condition a recursive call will keep calling itself indefinitely which will lead to a stack overflow.
2. Recursive Case
The function calls itself with a modified argument that moves towards the base case. This is used to break the problem into smaller subproblems. It is the reason why recursive functions are also called divide and rule approach methods.
3. Returning Results
The function usually returns a value that propagates back through the recursive calls.
Recursive Function Formulas
Recursive functions are defined by “Arithmetic Progressions” which consist of the first term followed by the other terms in the sequence. We also have a common difference between each term which we can calculate by subtracting both numbers.
| a(n) = a(n-1) + a(1) |
A recursive function can also be defined as a “Geometric sequence” where the sequence moves ahead using a common ratio.
| a(n) = r x a (n-1) |
Where r is the common ratio used to find the geometric progression.
Read more: How to use C Programming for Recursion?
Why are we using Recursive Functions?
Recursive functions provide a list of benefits which can be used to solve a problem by breaking them into smaller subproblems and then applying logic to get to the solution easily. Let us check some of the major benefits of using a recursive function.
1. Solving Complex problems
Recursion methods can easily be used to approach a complex problem into smaller subproblems. This approach will get you results and also provide a clear concise code.
2. Readable Program
Recursive programs are generally concise and simple to read and understand making them easy to read and execute.
3. Divide and Conquer Approach
Recursive functions use the divide and conquer approach to break a problem into a series of subproblems and integrate a logic to execute the problem. It is frequently used to solve sorting problems, backtracking and other problems.
4. Backtracking
Recursion can be used to solve problems with backtracking where every node is visited and solved again. It is used to solve dynamic programming problems such as sudoku and N-queens problems.
5. Tree and Graph Structures
With recursive functions tree and graph traversals become an easy task. It is very much easy to run pattern recognition tasks using the recursive functions.
Examples of a Recursive Function
Let us try to understand recursive functions with the help of some running examples. We can use different programming languages to run the solutions of these problems.
1. Factorial of a Number using Recursive Functions
Let us calculate the factorial of a number using the recursion method. Suppose we have a number n then the factorial of a number n will be given by
| #include <stdio.h>
int factorial(int n) { if (n == 0 || n == 1) // Base case return 1; return n * factorial(n – 1); // Recursive case } int main() { int num = 4; printf(“Factorial of %d is %d\n”, num, factorial(num)); return 0; } |
Python Example
| def factorial(n):
if n == 0 or n == 1: # Base case return 1 return n * factorial(n – 1) # Recursive case print(“Factorial of 4:”, factorial(4)) |
2. Reverse a string using Recursion
We can easily reverse the order of a string using the recursion method. Let us try to implement it below.
| #include <stdio.h>
#include <string.h> void reverseString(char str[], int start, int end) { if (start >= end) return; // Base case char temp = str[start]; str[start] = str[end]; str[end] = temp; reverseString(str, start + 1, end – 1); // Recursive case } int main() { char str[] = “hello”; reverseString(str, 0, strlen(str) – 1); printf(“Reversed string: %s\n”, str); return 0; } |
Python Example
| def reverseString(s):
if len(s) == 0: return s return reverseString(s[1:]) + s[0] # Recursive case print(“Reversed string:”, reverseString(“hello”)) |
What Makes a Function Recursive?
Recursive function is marked by using repeated function calls i,e. Directly or indirectly. But the most important recognition of a recursive function is whether we know the previous term, if we know we can tell that a function is recursive or not. Another important recognition of a recursive function is the base case which is a parameter used to stop the repeated function calls of a recursive function.
Try removing the base case from the function and execute the program, you will notice indefinite output results which will show that the function is recursive. If a function is calling itself or other function inside it then the function can be termed as a recursive function.
Learn Python Programming With PW Skills
Become a skilled Python developer with the knowledge of Data Structures in Python. Get enrolled in PW Skills Decode DSA With Python Course and get in-depth tutorials, practice exercises, real world projects and more with this self paced learning program.
You will learn through industry oriented curriculum and prepare for competitive programming with this course. Get a industry recognised certification from PW Skills after completing the course.
Recursive Functions FAQs
Q1. What is Recursive Function?
Ans: A Recursive function is a function which calls itself using its previous values to generate an additional set of values until a base condition is reached.
Q2. Give examples of problems solved using recursion?
Ans: Some of the problems such as factorial, fibonacci series, quick sort, merge sort, dynamic programming, N-queens problem, Tower of Hanoi, backtracking, tree traversal can be solved using recursive functions.
Q3. What are three major components of recursive functions?
Ans: The three major components of a recursive function are listed below.
1. Base case
2. Recursive calls
3. Return results
Q4. What is a base case in recursive functions?
Ans: A base case is a condition which is used to stop a recursive function call after a certain number of times. It prevents the recursive function from running for an indefinite time.
