Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a recursive function?
3.
Need of Recursive Function:
4.
Examples of Recursive Functions
4.1.
Fibonacci Sequence
4.2.
Java
4.3.
Factorial Function
4.4.
Java
4.5.
Binary Search
4.6.
Java
4.7.
Towers of Hanoi
4.8.
Java
5.
How does a recursive function call itself?
5.1.
Java
6.
Implementing Recursive Functions in Different Programming Languages
6.1.
Python
6.2.
JavaScript
7.
Role of Base Cases in Recursive Functions
8.
Benefits of Using Recursive Functions
9.
Challenges with Recursive Functions
10.
Frequently Asked Questions
10.1.
What is a recursive function in C logic?
10.2.
What are the two types of recursive functions?
10.3.
What is the difference between recursion and recursive function?
10.4.
What are some common use cases for recursive functions?
10.5.
What is the role of base cases in recursive functions, and why are they important?
11.
Conclusion
Last Updated: Mar 27, 2024
Medium

Recursive Functions

Author Gaurav Singh
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Hi Ninjas, in this blog, we will understand recursive functions. A recursive function is a technique that defines a function and then calls it itself. This way, finding answers to the most complex problems becomes easier. Some of the implementations of recursive functions are finding factorials, binary search, finding the sum of n numbers, etc., which we will see later in the blog.

One such problem that becomes very easy is Towers of Hanoi (TOH) using recursive functions. It is used to make our problems much simpler and more elaborate and helps us avoid “for loop” since it calls the function itself while computing the value of the recursive function.

Recursive Functions

In this blog, we will see how the Recursive Functions work and how to implement them using Java. We will also see the benefits and challenges of using recursive functions. Lastly, we will see multiple examples of how recursive functions can help us solve complex problems more easily.

What is a recursive function?

A recursive function is a programming function that calls itself to solve a problem by breaking it down into smaller, identical subproblems. Each recursive call works on a reduced version of the original problem until a base case is reached. It provides a solution for that base case and then combines results to solve the overall problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Need of Recursive Function:

Recursive functions are necessary for solving problems that can be broken down into smaller, similar subproblems. They simplify complex tasks, making your code more elegant, readable, and efficient by calling themselves with different inputs. Some examples of problems that are solved with recursive functions are quick sort, merge sort, factorial calculation, Fibonacci series, etc.

Examples of Recursive Functions

Fibonacci Sequence

  • Java

Java

public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}

 

The above code uses a recursive function called “fibonacci” with the input integer “n” to compute the nth term of the Fibonacci Series. Here, the base case is defined as when n is less than or equal to 1, the code will return n. Else, the function calls the “fibonacci” function with the input value as “n-1” and “n-2” and returns the addition of those two values returned by the “fibonacci” function.

Must Read Fibonacci Series in JavaScript

Factorial Function

  • Java

Java

public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}

 

The recursive algorithm for finding a factorial of a number is used in the above code. When n is zero, the function returns 1, which is the base case. If not, the function multiplies n by the factorial of n-1, which is calculated by calling the recursive function repeatedly with the argument n-1.

Binary Search

  • Java

Java

public static int binarySearch(int[] arr, int x, int low, int high) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binarySearch(arr, x, low, mid - 1);
} else {
return binarySearch(arr, x, mid + 1, high);
}
}
return -1;
}


The recursive algorithm for performing a binary search on an integer array is shown in the above code. There are four arguments for this function: the array, the value to search for, and the low and high indices of the subarray to search. The base case happens when the subarray is empty (high < low), in which case the capability returns - 1. If not, the function calculates the subarray's midpoint and determines whether the value to search for is equal to the midpoint element. The function returns the midpoint if it is. Otherwise, the function calls itself recursively on the left half of the subarray (low to mid-1) if the value is less than the element at the midpoint; otherwise, it calls itself recursively on the right half of the subarray (mid+1 to high).

Towers of Hanoi

  • Java

Java

public static void towersOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
System. out.println("Move disk 1 from rod " + from_rod + " to rod " + to_rod);
return;
}
towersOfHanoi(n-1, from_rod, aux_rod, to_rod);
System.out.println("Move disk " + n + " from rod " + from_rod + " to rod " + to_rod);
towersOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

 

The Towers of Hanoi problem is solved with the help of this code, which uses a recursive algorithm to move a stack of disks from one rod to another while keeping in mind that a larger disk cannot be placed on top of a smaller disk. There are four options for the function: the names of the rods and the number of disks. The function prints a message instructing the disk to be moved from the starting rod to the destination rod in the base case, which occurs when only one disk exists.

Must Read Recursion in Data Structure

How does a recursive function call itself?

Recursive Functions call themselves during the execution of the function. It allows the function to repeat a set of instructions multiple times. This goes on until a certain condition is met, at which point the function terminates and returns a value.

  • Java

Java

public static void count_down(int n) {
   if (n == 0) {
       System.out.println("Blast off!");
   } else {
       System.out.println(n);
       count_down(n - 1);
   }
}


Let's understand the above code line by line

function count_down(n):


The above function is defined as “count_down()”, which takes “n” as input. 

    if n == 0:
        print("Blast off!")


The above code is called the base condition. Any function first checks this condition. If this is true, then the function returns the predefined value. Otherwise, it will go to another condition, i.e., else condition. Here, if n is equal to 0, then the function prints “Blast Off”.

    else:
        print(n)
        count_down(n - 1)


Now, if the above base condition was False, then this else condition will be executed, which uses the recursive function “count_down()”. So, if n is not equal to 1, then the function calls recursively with “n-1” as the new input.

So basically, this recursive call pauses the current execution of the function and makes a new instance of the function with a new input value. Thus, this will perform the same steps as the function did with any other value of n (apart from n equal to being 1, which is the base condition). This recursive function will be executed until the value of n is equal to 1 or, say, the function satisfies the base condition.

The pseudo-output for the above code looks like this for every recursive function instance:

count_down(5) --> print five
count_down(4) --> print 4
count_down(3) --> print three
count_down(2) --> print two
count_down(1) --> print one
count_down(0) --> print "Blast off!"

Thus the final output would look like this:

5
4
3
2
1
Blast off

Implementing Recursive Functions in Different Programming Languages

We will make a recursive function to calculate the factorial of an nth number.

In Python:

  • Python

Python

def factorial(n):
   if n == 0:
       return one
   else:
       return n * factorial(n - 1)


In JavaScript:

  • JavaScript

JavaScript

function factorial(n) {
   if (n == 0) {
       return 1;
   } else {
       return n * factorial(n - 1);
   }
}


Both of these functions take “n” (supposing 5 in this case) as an input, and the base condition is that if n is equal to 0, then the function would return the value of 1. While if the base condition os not true, then the else condition will be executed which calculates the multiplication of n and ‘factorial(n-1)’. Here factorial(n-1) is a recursive function that returns a new value when run. This is continued until the base condition is true.

The pseudo-output for the above code looks like this for every recursive function instance:

factorial(3)
    returns 3 * factorial(2)


    factorial(2)
        returns 2 * factorial(1)


        factorial(1)
            returns 1 * factorial(0)


            factorial(0)
                returns 1


            returns 1 * 1 = 1


        returns 2 * 1 = 2


    returns 3 * 2 = 6


Output

6

Role of Base Cases in Recursive Functions

A base case is a condition that permits the capability to end the recursion and return a worth. The function would continue to call itself indefinitely without a base case, resulting in an infinite loop and eventual program failure.

The base case for the count_down example is when the input value reaches zero. Right now, the capability returns the "Blast off!" message, and the Recursion comes to an end.

In the factorial model, the base case is the point at which the input value is 0. The function returns 1 and the recursion stops because the 0 factorial is defined as 1.

Having a well-defined base case is necessary for the right functioning of recursive functions. It ensures that the recursion stops at the right time and keeps the program from crashing because of an infinite loop. All in all, recursive functions are an integral tool that permits us to separate complex issues into smaller sub-problems. They use a clearly defined base case to terminate the recursion and call themselves during execution. The fundamental structure of recursive functions can be implemented in a variety of programming languages.

Benefits of Using Recursive Functions

Recursive functions offer a few benefits over iterative capabilities. One of their essential advantages is their simplicity and readability for developers. Recursive functions can be more intuitive and straightforward to comprehend than iterative solutions because they frequently mirror the problem they are solving.

  • Recursive functions have the additional advantage of being able to deal with complex problems with minimal code. Code can often be written in a more concise and modular manner by breaking a problem into smaller subproblems and calling the function recursively.
     
  • Recursive functions are especially useful for simplifying complex problems with patterns that keep happening. Recursive functions, as opposed to iterative algorithms, can frequently offer a solution that is more intuitive and elegant because they divide a problem into smaller subproblems with similar structures.
     
  • Tree traversal is one example of a problem that can be solved with recursion. In computer science, trees are a common data structure for representing hierarchical relationships between data elements. The use of recursive algorithms to traverse a tree in either a depth-first or a breadth-first order makes it possible to process large data sets effectively.
     
  • Tail recursion is a method that reuses the same stack frame for each recursive call to optimize recursive functions. The recursive call is the function's last operation in a tail-recursive function. After the recursive call, the function does not need to perform any additional operations or return any additional values.
     
  • By eliminating the requirement for extra stack frames, tail recursion optimization can essentially work on the performance of recursive capabilities, especially in situations where the function is called with huge data inputs. Additionally, this optimization may reduce the risk of errors caused by stack overflows.

Challenges with Recursive Functions

Recursive functions are powerful techniques to solve complex problems. However, there are some problems or say challenges that occur while using Recursive Functions. The main 2 problems that arise are:

  1. Stack Overflow: One normal issue with recursive functions is the chance of a stack overflow. Every time a function calls itself, a new stack frame is created. The stack may become full and the program may crash if the recursion goes too far. Particularly for languages that do not support tail recursion optimization, this may be a concern.
     
  2. Inefficient Programming: Recursive functions face another challenge, which is that they may occasionally be less effective than iterative algorithms. Because each recursive call creates a new stack frame, recursive functions typically have a higher memory overhead than their iterative counterparts. Additionally, because they can be optimized for hardware-specific features like caching, some algorithms may be better suited to iterative approaches.
     

Regardless of these difficulties, there are systems for streamlining recursive functions to limit these issues. Using tail recursion optimization, which reuses the existing frame for each recursive call, can eliminate the need for multiple stack frames. Another procedure is to restrict the profundity of the recursion by setting the most extreme number of recursive calls or by involving a non-recursive calculation for enormous data sources. Furthermore, calculations can be enhanced for memory use by utilizing dynamic programming or memoization strategies.

Frequently Asked Questions

What is a recursive function in C logic?

A recursive function in C is a function that calls itself to solve a problem by breaking it down into smaller, similar subproblems, simplifying complex tasks.

What are the two types of recursive functions?

The two types of recursion are -- tail recursion which has the recursive call as the last operation and non-tail recursion which has some operations after the recursive call.

What is the difference between recursion and recursive function?

Recursion is a problem-solving approach where a function calls itself, while a recursive function is the actual implementation of this approach, containing the recursive call.

What are some common use cases for recursive functions?

Tree traversal and manipulation are the common use cases of recursive functions.

What is the role of base cases in recursive functions, and why are they important?

Base cases are necessary in recursive functions since they help terminate the function when the base case is satisfied. Otherwise, the function will keep calling it infinite times, which will ultimately crash the compile and cause a stack overflow error.

Conclusion

Thus, in this blog, we have studied the recursive functions, and we saw how the recursive functions are implemented. We saw that recursive functions are one of the important techniques to solve complex problems in an easier way by dividing them into smaller subsection problems. We also learned about the benefits of using recursive functions and saw the common challenges faced while implementing them. At last, we saw multiple exams on solving problems using recursive functions.

To learn more about recursive functions, you can visit the following blogs:

Recursion

Backtracking and Recursion.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles interview experiences, and interview bundle for placement preparations. Read our blogs on aptitudecompetitive programminginterview questionsIT certifications, and data structures and algorithms for the best practice.

Previous article
Reverse a String Using Recursion
Next article
What is Recursive Function in C
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass