Recursion Algorithms
Recursion is technique used in computer science to solve big problems by breaking them into smaller, similar problems. The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily.
What is Recursion?
Recursion is a programming technique where a function calls itself within its own definition. This allows a function to break down a problem into smaller subproblems, which are then solved recursively.
How Does Recursion Work?
Recursion works by creating a stack of function calls. When a function calls itself, a new instance of the function is created and pushed onto the stack. This process continues until a base case is reached, which is a condition that stops the recursion. Once the base case is reached, the function calls start popping off the stack and returning their results.
What is a Recursive Algorithm?
A recursive algorithm is an algorithm that uses recursion to solve a problem. Recursive algorithms typically have two parts:
- Base case: Which is a condition that stops the recursion.
- Recursive case: Which is a call to the function itself with a smaller version of the problem.
Types of Recursion
There are several different recursion types and terms. These include:
- Direct recursion: This is typified by the factorial implementation where the methods call itself.
- In-Direct recursion: This happens where one method, say method A, calls another method B, which then calls method A. This involves two or more methods that eventually create a circular call sequence.
- Head recursion: The recursive call is made at the beginning of the method.
- Tail recursion: The recursive call is the last statement.
When to Use Recursion?
Recursion is a powerful technique that can be used to solve a wide variety of problems. However, it is important to use recursion carefully, as it can lead to stack overflows if not used properly.
Recursion should be used when:
- The problem can be broken down into smaller subproblems that can be solved recursively.
- The base case is easy to identify.
- The recursive calls are tail recursive.
Examples of Recursion
Here are some common examples of recursion:
Example 1: Factorial: The factorial of a number n is the product of all the integers from 1 to n. The factorial of n can be defined recursively as:
factorial(n) = n * factorial(n-1)
Example 2: Fibonacci sequence: The Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding numbers. The Fibonacci sequence can be defined recursively as:
fib(n) = fib(n-1) + fib(n-2)
Applications of Recursion Algorithms:
Here are some common applications of recursion:
- Tree and Graph Traversal: Depth-first search (DFS) and breadth-first search (BFS)
- Dynamic Programming: Solving optimization problems by breaking them into smaller subproblems
- Divide-and-Conquer: Solving problems by dividing them into smaller parts, solving each part recursively, and combining the results
- Backtracking: Exploring all possible solutions to a problem by recursively trying different options
- Combinatorics: Counting or generating all possible combinations or permutations of a set
Learn Basics of Recursion Algorithms:
- Introduction to Recursion – Data Structure and Algorithm Tutorials
- What is Recursion?
- Difference between Recursion and Iteration
- Types of Recursions
- Finite and Infinite Recursion with examples
- What is Tail Recursion
- What is Implicit recursion?
- Why is Tail Recursion optimization faster than normal Recursion?
- Recursive Functions
- Difference Between Recursion and Induction
Recursion in Different Languages:
Easy Problems on Recursion
- Print 1 to n without using loops
- Print N to 1 without loop
- Mean of Array using Recursion
- Sum of natural numbers using recursion
- Decimal to binary number using recursion
- Sum of array elements using recursion
- Print reverse of a string using recursion
- Program for length of a string using recursion
- Sum of digit of a number using recursion
- Tail recursion to calculate sum of array elements.
- Program to print first n Fibonacci Numbers | Set 1
- Program for factorial of a number
- Recursive Programs to find Minimum and Maximum elements of array
- Recursive function to check if a string is palindrome
- Count Set-bits of number using Recursion
- Print Fibonacci Series in reverse order using Recursion
- Coin Change | DP-7
Medium Problems on Recursion
- Recursively remove all adjacent duplicates
- Sort the Queue using Recursion
- Reversing a queue using recursion
- Binary to Gray code using recursion
- Delete a linked list using recursion
- Product of 2 Numbers using Recursion
- Programs for Printing Pyramid Patterns using Recursion
- Length of longest palindromic sub-string : Recursion
- Program for Tower of Hanoi Algorithm
- Time Complexity Analysis | Tower Of Hanoi (Recursion)
- Program to calculate value of nCr using Recursion
- Find geometric sum of the series using recursion
- Convert a String to an Integer using Recursion
- DFS traversal of a Tree
- Bottom View of a Binary Tree using Recursion
- Write a program to print all Permutations of given String
- Print all subsets of a given Set or Array
- Print all possible paths from top left to bottom right of a mXn matrix
- Print all combinations of balanced parentheses
- Longest Common Subsequence (LCS)
Hard Problems on Recursion
- Find the value of a number raised to its reverse
- How to Sort a Stack using Recursion
- Reverse a Doubly linked list using recursion
- Given a string, print all possible palindromic partitions
- Check if a string is a scrambled form of another string
- Word Break Problem | DP-32
- Print all palindromic partitions of a string
- N Queen Problem | Backtracking-3
- Algorithm to Solve Sudoku | Sudoku Solver
- The Knight’s tour problem
Practice Sets on Recursion
- Recursive Practice Problems with Solutions
- Practice Questions for Recursion | Set 1
- Practice Questions for Recursion | Set 2
- Practice Questions for Recursion | Set 3
- Practice Questions for Recursion | Set 4
- Practice Questions for Recursion | Set 5
- Practice Questions for Recursion | Set 6
- Practice Questions for Recursion | Set 7
- Practice questions for Linked List and Recursion
Quiz based on Recursion:
Contact Us