Recursion Basics: Day 7 of DSA Challenge

Recursion is a fundamental concept in programming, where a function calls itself to solve smaller instances of a problem. Today's problems revolved around exploring the power of recursion for various tasks.

1. Calculate the Factorial of a Number

The factorial of a number n is the product of all positive integers less than or equal to n. A recursive function can elegantly solve this by defining n!=n×(n−1)! with 0!=1.

import java.util.Scanner;

public class Factorial {
    public static int Factorial(int n){
        if(n==1 || n==0)
            return 1;
        return n*Factorial(n-1);
    } 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number: ");
        int n = sc.nextInt();

        System.out.println("Factorial: "+Factorial(n));
    }
}

2. Tower of Hanoi for 3 Disks

The Tower of Hanoi involves moving disks from one rod to another, following the rules:

Only one disk can be moved at a time.
A disk can only be placed on top of a larger disk.

The task is to move all disks from the source rod to the destination rod using an auxiliary rod.

  public class TowerOfHanoi {
      public static void solveHanoi(int n, char source, char destination, char auxiliary) {

          if (n == 1) {
              System.out.println("Move disk 1 from " + source + " to " + destination);
              return;
          }

          solveHanoi(n - 1, source, auxiliary, destination);

          System.out.println("Move disk " + n + " from " + source + " to " + destination);

          solveHanoi(n - 1, auxiliary, destination, source);
      }

      public static void main(String[] args) {
          int disks = 3; 
          System.out.println("Steps to solve Tower of Hanoi for " + disks + " disks:");
          solveHanoi(disks, 'A', 'C', 'B'); 
      }
  }

3. Print All Subsequences of a String

A subsequence is any sequence derived from a string by deleting some or no characters without changing the order of the remaining characters. This problem is ideal for recursion, as it involves exploring all combinations of including or excluding each character.

import java.util.Scanner;

public class Subsequences {
    public static void printSubsequences(String str, String current, int index) {
        if (index == str.length()) {
            System.out.println(current);
            return;
        }
        printSubsequences(str, current + str.charAt(index), index + 1);
        printSubsequences(str, current, index + 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the string: ");
        String str = sc.nextLine();
        printSubsequences(str, "", 0);
    }
}

4. Find the nth Fibonacci Number

The Fibonacci sequence is defined as:
F(n)=F(n−1)+F(n−2)
with base cases F(0)=0 and F(1)=1. A recursive function captures this directly by expressing F(n)F(n) in terms of smaller subproblems.

import java.util.Scanner;

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the value of n: ");
        int n = sc.nextInt();
        System.out.println("Fibonacci number " + n + " is " + fibonacci(n));
    }
}

5. Sum of Digits in a Number

This problem involves finding the sum of the digits of a number recursively. The problem can be reduced to adding the last digit of the number to the sum of the digits of the number formed by removing the last digit.

import java.util.Scanner;

public class SumOfDigits {
    public static int sumOfDigits(int num) {
        if (num == 0) return 0;
        return num % 10 + sumOfDigits(num / 10);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number: ");
        int num = sc.nextInt();
        System.out.println("Sum of digits: " + sumOfDigits(num));
    }
}

Reflection

Recursion is both powerful and elegant, allowing complex problems to be solved by breaking them into simpler subproblems. While it requires careful handling of base cases and termination conditions, mastering recursion is essential for algorithm design.

Looking forward to tackling more recursion problems on Day 8! 🚀

Day 7 of 100 Days of DSA Challenge: Recursion Basics

Table of contents