What is the process called as when a method calls itself again with its structure?
What do you mean by recursion?Recursion means “solving a problem using the solution of smaller subproblems (smaller version of the same problem)” or “defining a problem in terms of itself”. This is a widely used idea in data structures and algorithms to solve complex problems by breaking them down into simpler ones. In this blog, we will understand the fundamentals of recursion and help you refine an essential programming skill. Show
Recursion comes up in mathematics frequently, where we can find many examples of expressions written in terms of themselves. For example, calculating the value of nth factorial and nth Fibonacci numbers is one of the best examples. But recursion is just as much a programming concept!
H ow recursion works in real life?Suppose you are standing in a long queue of people. How many people are directly behind you in the line? Rules
Solution
H ow recursion works in programming?In programming terms, recursion is a function calling itself until a “base condition” is true to produce the correct output.
In other words: To solve a problem, we solve a problem that is a smaller instance of the same problem, and then use the solution to that smaller instance to solve the original problem. For a recursive algorithm to work, smaller subproblems must eventually arrive at the base case. In simple words, any recursive algorithm has two parts: base case and recursive structure. Base caseB ase case is a terminating condition where a function immediately return the result. This is the smallest version of the problem for which we already know the solution. Recursive structureR ecursive structure is an idea to design a solution of a problem via the solution of its smaller sub-problems i.e. same problem but for a smaller input size. We continue calling the same problem for smaller input sizes until we reach the base case of recursion. Steps of problem-solving using recursion
I deas to keep in mind while working with recursion
Basic examples of recursive functionsCalculate the sum of two numbers using recursion
Calculate the product of two numbers using recursion
Calculate the power of two numbers using recursion
Understanding recursion via finding nth FactorialThe factorial of a non-negative integer is a multiplication of all integers smaller than or equal to n. For example. the factorial of 5 is 1 * 2 * 3 * 4 * 5 = 120 Recursive structureAccording to the mathematical definition of the factorial of n, we can write:
If we calculate the value of the (n - 1)th factorial, we can easily calculate the value of the nth factorial. It means we can solve the problem of input size n with its smaller problem of the input size (n - 1). In other words, we can solve this problem by using the idea of recursion! Suppose the function fact(n) and fact(n - 1) return the value of the nth and (n - 1)th factorial, respectively, then we can write the following recursive structure:
Base caseIn every recursive solution, there must be a terminating condition or base case where our recursion will directly give us results without breaking it again into the sub-problem. If we observe the above recursive structure, then we find the following chain of recursive calls behind the scene:
The factorial of a negative number is not defined, so fact(0) is the smallest version of the factorial problem where our recursion will terminate and return the value directly. So n = 0 is the base case that will return the value 1. Recursive pseudocode of nth Factorial
How recursion works in the background?If we draw the flow of recursion for the factorial program, one can find this pattern: we are calling fact(0) last, but it is returning the value first. Similarly, we are calling fact(n) first, but it is returning the value last. Did you find some Last In First Out (LIFO) orders for recursive calls and return values? Yes, you got it right! Behind the scene, the compiler uses a stack data structure to simulate recursion and deliver the correct output. We call this stack: Call Stack!
How the idea of call stack work in recursion?
Visualization for calculating fact(5) using recursion Examples of some famous recursive algorithmsReverse an arrayRecursive structure: reverse (A[], l, r) = swap(A[l], A[r]) + reverse(A, l+1, r-1) Base case: if (l >= r) then return Recurrence relation: T(n) = T(n - 2) + c, Time complexity = O(n) Finding the GCD of two numbersRecursive structure: GCD(a, b) = GCD(b, a mod b), here a > b Base case: GCD(a, 0) = a Recurrence relation: T(n) = T(n/d) + c, where d is a decreasing factor, Time complexity = O(log b) Finding the nth FibonacciRecursive structure: fib(n) = fib(n-1) + fib(n-2) Base case: We have 2 base cases: fib(0) = 0 and fib(1) = 1 Recurrence relation: T(n) = T(n-1) + T(n-2) + c, Time complexity = O(2^n) Tower of Hanoi problemRecursive structure: We move a stack of n disks from peg X to Y using peg Z
Base case: If n = 1, move disk from X to Y Recurrence relation: T(n) = 2 T(n-1) + c, Time complexity = O(2^n) Binary Search AlgorithmRecursive structure: binarySearch(A[], l, r, k)
Base case: If (l > r) then return -1 Recurrence relation: T(n) = T(n/2) + c, Time complexity = O(log n) Merge Sort AlgorithmRecursive structure: mergeSort (A[], l, r)
Base case: if (l == r) then return. This is a case of a single-element array. Recurrence relation: T(n) = 2 T(n/2) + cn, Time complexity = O(n log n) Quick Sort AlgorithmRecursive structure: quickSort(A[], l, r)
Base case: if (l >= r) then return. Recurrence relation: T(n) = Sum (i = 0 to n - 1) [T(i) + T(n - i - 1)]/ n, Time complexity = O(nlogn) [Average case analysis] Reverse a Linked ListRecursive structure: reverseList(Node head)
Base case: if (head == NULL || head->next == NULL), return head Recurrence relation: T(n) = T(n - 1) + c, Time complexity = O(n) Post-order Traversal of a Binary Tree Recursive structure: postorder(root)
Base case: if(root == NULL), then return Recurrence relation: T(n) = T(n - 1) + c, Time complexity = O(n) Print all permutation of a given string Recursive structure: permute(S[], l, r)
Base case: if(l == r) then print(A) Recurrence relation: T(n) = sum (i = 0 to n - 1) [T(n - i) + c], Time complexity = O(n!) Stack overflow error in recursionWhen we call a recursive function, the return address and arguments are pushed onto the call stack. The stack is finite, so if the recursion is too deep, you'll eventually run out of stack space. This is also called the stack overflow in recursion. In some situations, if the recursive function is tail-recursive, some compilers might optimize the recursive call away by turning it into a jump. Popular reasons for stack overflow error:
Common mistakes in recursive implementationsHere are two common ways that a recursive implementation can go wrong:
Look for these when you are debugging. On the bright side, an infinite loop in an iterative implementation usually becomes a stack overflow error in a recursive implementation. A buggy recursive program fails faster! A nalysis of recursive algorithmsThe basic idea of recursion analysis is: Calculate the total number of operations performed by recursion at each recursive call and do the sum to get the overall time complexity. So when recursion is doing constant operation at each recursive call, we just count the total number of recursive calls. Otherwise, the analysis will be a little mathematical if the operation count at each recursive call depends on the input size. Overall, there are several techniques to analyse recursion: Substitution method, Recursion tree method, and Master theorem.
Explore this blog to learn recursion analysis: Analysis of Recursion in data structure and algorithms Recursion Vs. Iteration
E xplore this blog for more details: Iteration vs Recursion comparison Application of recursion in problem-solving
Concepts to explore further
Coding problems to practice using recursion
Content references
Enjoy learning, Enjoy coding, Enjoy algorithms! What is the process called as when a method calls itself again within its structure?In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code.
What is the phenomenon called when a function calls itself?The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.
What is recursive call in data structure?Recursion in data structure is when a function calls itself indirectly or directly, and the function calling itself is known as a recursive function. It's generally used when the answer to a larger issue could be depicted in terms of smaller problems.
What is a method that calls itself in Java?In Java, a method that calls itself is known as a recursive method. And, this process is known as recursion. A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.
|