What is Recursion?
Recursion is a programming approach where a function repeats an action by calling itself, either directly or indirectly. This enables the function to continue performing the action until a particular condition is satisfied, such as when a particular value is reached or another condition is met.
What is Implicit Recursion?
A specific sort of recursion called implicit recursion occurs when a function calls itself without making an explicit recursive call. This can occur when a function calls another function, which then calls the original code once again and starts a recursive execution of the original function. This can sometimes be difficult to spot and can lead to unintended behavior if not handled carefully.
Example of the implicit recursion:
We will use implicit recursion to find the second-largest elements from the array:
C++14
#include <bits/stdc++.h>using namespace std;int findLargest(vector<int> numbers) { int largest = numbers[0]; for (int number : numbers) { if (number > largest) { largest = number; } } return largest;}int findSecondLargest(vector<int> numbers) { // Remove the largest number from the list numbers.erase(remove(numbers.begin(), numbers.end(), findLargest(numbers)), numbers.end()); // Return the largest remaining number return findLargest(numbers);}int main() { vector<int> numbers = {1, 2, 3, 4, 5}; // Function call int secondLargest = findSecondLargest(numbers); cout << secondLargest << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;import java.util.stream.Collectors;class GFG { public static int findLargest(List<Integer> numbers) { int largest = numbers.get(0); for (int number : numbers) { if (number > largest) { largest = number; } } return largest; } public static int findSecondLargest(List<Integer> numbers) { final int largest = findLargest(numbers); // Remove the largest number from the list numbers = numbers.stream() .filter(n -> n != largest) .collect(Collectors.toList()); // Return the largest remaining number return findLargest(numbers); } public static void main(String[] args) { List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5); // Function call int secondLargest = findSecondLargest(numbers); System.out.println(secondLargest); }}// This code is contributed by lokeshmvs21. |
Python3
def find_largest(numbers): largest = numbers[0] for number in numbers: if number > largest: largest = number return largestdef find_second_largest(numbers): # Remove the largest number from the list numbers.remove(find_largest(numbers)) # Return the largest remaining number return find_largest(numbers)# Driver codenumbers = [1, 2, 3, 4, 5]# Function callsecond_largest = find_second_largest(numbers)print(second_largest) |
C#
using System;using System.Collections.Generic;class GFG { public static int findLargest(List<int> numbers) { int largest = numbers[0]; for (int i = 1; i < numbers.Count; i++) { if (numbers[i] > largest) { largest = numbers[i]; } } return largest; } public static int findSecondLargest(List<int> numbers) { int largest = findLargest(numbers); // Remove the largest number from the list numbers.Remove(largest); // Return the largest remaining number return findLargest(numbers); } public static void Main(string[] args) { List<int> numbers = new List<int>{ 1, 2, 3, 4, 5 }; // Function call int secondLargest = findSecondLargest(numbers); Console.WriteLine(secondLargest); }}// This code is contributed by aadityamaharshi21. |
Javascript
function findLargest(numbers) { let largest = numbers[0]; for (let number of numbers) { if (number > largest) { largest = number; } } return largest;}function findSecondLargest(numbers){ // Remove the largest number from the list numbers = numbers.filter(n => n !== findLargest(numbers)); // Return the largest remaining number return findLargest(numbers);}let numbers = [1, 2, 3, 4, 5];// Function calllet secondLargest = findSecondLargest(numbers);console.log(secondLargest);// This code is contributed by aadityamaharshi21. |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
In this case, the find_second_largest( It’s crucial to remember that explicit recursion could also be used to accomplish this example, which would make the code simpler to read and comprehend. ) method calls the find_largest() function via implicit recursion to locate the second-largest number in a provided list of numbers. Implicit recursion can be used in this way to get the second-largest integer without having to write any more code, which is a handy use.
Problem with implicit recursion:
In the case of the implicit recursion, the issue of an infinite function call may occur. Here is a case where implicit recursion can cause the problem:
C++
#include <iostream>using namespace std;void func2();void func1();void func1() { cout << "This is the first function" << endl; func2();}void func2() { cout << "This is the second function" << endl; func1();}int main() { func1(); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static void func1(){ System.out.println("This is the first function"); func2(); } static void func2(){ System.out.println("This is the second function"); func1(); } public static void main (String[] args) { func1(); }}// This code is contributed by lokeshmvs21. |
Python3
def func1(): print("This is the first function") func2()def func2(): print("This is the second function") func1()func1() |
C#
using System;public class GFG { static void func1() { Console.WriteLine("This is the first function"); func2(); } static void func2() { Console.WriteLine("This is the second function"); func1(); } static public void Main() { // Code func1(); }}// This code is contributed by lokesh. |
Javascript
// Define func2function func2() { console.log("This is the second function"); // Call func1 inside func2 func1();}// Define func1function func1() { console.log("This is the first function"); // Call func2 inside func1 func2();}// Call func1 from mainfunc1(); |
Output:
This is the first function This is the second function This is the first function This is the second function ... ...
In this example, the func1() function calls func2(), which then calls func1() once again.
Steps to avoid this issue:
- When utilizing implicit recursion, caution must be taken since if the recursive calls are not handled correctly, it is simple to produce an endless loop.
- Additionally, it’s typically recommended to avoid implicit recursion if feasible because it might make your code more challenging to read and maintain.
- Instead, explicit recursion, which is simpler to read and understand, is typically preferred.
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
