Dsa Full cource

 Skip to content

 Recursion Algorithms By Umang

Last Updated : 03 Apr, 2024

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.

Recursion-Algorithm.png

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:

Recursion in Different Languages:

Easy Problems on Recursion

Medium Problems on Recursion

Hard Problems on Recursion

Practice Sets on Recursion

Quiz based on Recursion:



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
News
Previous Article
Sorting Algorithms
Next Article
Backtracking Algorithm
Read MoreDown Arrow

Similar Reads

Why is Tail Recursion optimization faster than normal Recursion?
What is tail recursion? Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. What is non-tail recursion? Non-tail or head recursion is defined as a recursive function in which the recursive call is the f
4 min read
The Great Tree-List Recursion Problem.
Asked by Varun Bhatia. Question: Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The”previous” pointers should be stored in the “small” field and the “next” pointers should be stored in the “large” field. The list sho
1 min read
Practice questions for Linked List and Recursion
Assume the structure of a Linked List node is as follows. C/C++ Code struct Node { int data; struct Node *next; }; // This code is contributed by SHUBHAMSINGH10 C/C++ Code struct Node { int data; struct Node *next; }; Java Code static class Node { int data; Node next; }; // This code is contributed by shubhamsingh10 C/C++ Code class Node: def __ini
11 min read
Practice Questions for Recursion | Set 1
Explain the functionality of the following functions. Question 1 C/C++ Code int fun1(int x, int y) { if (x == 0) return y; else return fun1(x - 1, x + y); } C/C++ Code int fun1(int x, int y) { if (x == 0) return y; else return fun1(x - 1, x + y); } Java Code static int fun1(int x, int y) { if (x == 0) return y; else return fun1(x - 1, x + y); } C/C
5 min read
Practice Questions for Recursion | Set 2
Explain the functionality of the following functions. Question 1 C/C++ Code /* Assume that n is greater than or equal to 1 */ int fun1(int n) { if (n == 1) return 0; else return 1 + fun1(n / 2); } Java Code /* Assume that n is greater than or equal to 1 */ static int fun1(int n) { if (n == 1) return 0; else return 1 + fun1(n / 2); } C/C++ Code # As
3 min read
Practice Questions for Recursion | Set 4
Question 1 Predict the output of the following program. C/C++ Code #include <iostream> using namespace std; void fun(int x) { if(x > 0) { fun(--x); cout << x <<" "; fun(--x); } } int main() { int a = 4; fun(a); return 0; } // This code is contributed by SHUBHAMSINGH10 C/C++ Code #include<stdio.h> void fun(int x)
6 min read
Practice Questions for Recursion | Set 5
Question 1Predict the output of the following program. What does the following fun() do in general? C/C++ Code #include <iostream> using namespace std; int fun(int a, int b) { if (b == 0) return 0; if (b % 2 == 0) return fun(a + a, b/2); return fun(a + a, b/2) + a; } int main() { cout << fun(4, 3) ; return 0; } // This code is contribut
5 min read
Practice Questions for Recursion | Set 7
Question 1 Predict the output of the following program. What does the following fun() do in general? C/C++ Code #include <iostream> using namespace std; int fun(int n, int* fp) { int t, f; if (n <= 2) { *fp = 1; return 1; } t = fun(n - 1, fp); f = t + *fp; *fp = t; return f; } int main() { int x = 15; cout << fun(5, &x) <<
4 min read
Print 1 to 100 in C++ Without Loops and Recursion
We can print 1 to 100 without using loops and recursion using three approaches discussed below: 1) Template Metaprogramming: Templates in C++ allow non-datatypes also as parameters. Non-datatype means a value, not a datatype. Example: C/C++ Code // CPP Program to print 1 to 100 // without loops and recursion #include <iostream> using namespac
3 min read
Print ancestors of a given binary tree node without recursion
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.For example, consider the following Binary Tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 Following are different input keys and their ancestors in the above tree Input Key List of Ancestors ------------------------- 1 2 1 3 1 4 2 1 5 2 1
15 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox

Comments

Post a Comment