Back to DSA Course

What is a Recursion?

Recursion is a way of solving a problem by having a function calling itself.

In Recursion, there must be some condition that will terminate the recursion.

Properties of Recursion

• Performing the same operation multiple times with different inputs.
• In every step, we try smaller inputs to make the problem smaller.
• Base condition is needed to stop the recursion, otherwise infinite loop will occur.

Note: Space complexity is not constant due to recursive calls.

Why we need Recursion

• Because it makes the code easy to write (compared to iterative) whenever a given problem can be broken down into similar sub-problem.
• Because it is heavily used in Data Structures like Tree, Graph etc.
• It is heavily used in techniques like Divide and Conquer,Greedy and Dynamic Programming etc.

Format of a Recursive Function

• Recursive Case: Case where the function recur.
• Base Case: Case where the function does not recur.

Recursion mainly uses stack memory as you know.

Recursive vs Iteration

• Space Efficient? Recursion –No, Iteration – Yes
• Time Efficient? Recursion –No, Iteration – Yes
• Ease of Code (to solve sub-problems)? Recursion –Yes, Iteration – No

When to use/Avoid Recursion?

When to use

• When we can easily breakdown a problem into similar sub-problem.
• When we are fine with extra overhead(both time and space) that comes with it.
• When we need a quick working solution instead of efficient one.
• When traverse a tree.

When to Avoid

• If time and space complexity matter for us.

Practical use of Recursion

• Fibonacci Series, Factorial Finding
• Sorting – Quick Sort and Merge Sort
• Binary Search
• Towers of Hanoi
• Tree - Traversal/Searching/Insertion/Deletion
• Graph - DFS(Depth First Search) and BFS(Breadth First Search)
• Divide and Conquer Algorithms
• Back Tracking Algorithms
• Dynamic Programming
• Stack

Let's see some programs

Sum of digits in a number

package com.praveen.recursion;

public class SumOfDigits {

	public static void main(String[] args) {
		System.out.println(sumofDigits(123));

	}

	public static int sumofDigits(int n) {

		if (n == 0 || n < 0) {
			return 0;
		}
		return n % 10 + sumofDigits(n / 10);
	}

}

Factorial of a number

package com.praveen.recursion;

import java.util.Scanner;

public class Factorial {

	 public static void main(String args[]) {
		 Scanner s= new Scanner(System.in);
		 System.out.println("Enter number for finding factorial of it");
		 int num=s.nextInt();
		 s.close();
		 System.out.println(factorial(num));
		
	 }

	private static int factorial(int num) {
		if(num==0) {
			return 1;
		}else {
			return num*factorial(num-1);
		}
	}
}

Fibonacci Series

package com.praveen.recursion;

public class FibonacciSeries {

	static int n1 = 0, n2 = 1, n3 = 0;

	static void printFibonacci(int count) {
		if (count > 0) {
			n3 = n1 + n2;
			n1 = n2;
			n2 = n3;
			System.out.print(" " + n3);
			printFibonacci(count - 1);
		}
	}

	public static void main(String args[]) {
		int count = 10;
		System.out.print(n1 + " " + n2);// printing 0 and 1
		printFibonacci(count - 2);// n-2 because 2 numbers are already printed
	}
}

Product of Array

package com.praveen.recursion;

public class ProductOfArray {

	public static void main(String[] args) {

		int[] num = { 1, 2, 3, 4, 5 };
		System.out.println(productofArray(num, num.length));

	}

	public static int productofArray(int[] num, int len) {
		if (len <= 0)
			return 1;
		return (productofArray(num, len - 1) * num[len - 1]);
	}
}

Reverse a String

package com.praveen.recursion;

public class ReverseAString {

	public static void main(String[] args) {
		System.out.println(reverse("praveen"));

	}

	public static String reverse(String str) {
		if (str.isEmpty())
			return str;
		return reverse(str.substring(1)) + str.charAt(0);
	}

}

Binary Search

package com.praveen.recursion;

public class BinarySearch {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 55, 66, 78 };
		int target = 78;
		System.out.println(search(arr, target, 0, arr.length - 1));

	}

	private static int search(int[] arr, int target, int s, int e) {
		if (s > e) {
			return -1;
		}
		int m = s + (e - s) / 2;
		if (arr[m] == target) {
			return m;
		}
		if (target < arr[m]) {
			return search(arr, target, s, m - 1);
		}
		return search(arr, target, m + 1, e);
	}

}