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:

1. Base case: Which is a condition that stops the recursion.
2. 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:

• Recursion in Python
• Recursion in Java
• Recursion in C#
• How to Understand Recursion in JavaScript?

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: