Day 7 of the 100 Days DSA Challenge: Recursion Basics

Welcome to Day 7 of the 100 Days DSA Challenge! Today, we will explore the fascinating world of recursion. Recursion allows us to solve problems by breaking them down into smaller, simpler sub-problems. We'll tackle some essential recursion problems using C language. Let's dive in!

1. Calculate the Factorial of a Number

Problem: Write a recursive function to calculate the factorial of a number.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int number = 5;
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

2. Tower of Hanoi Problem

Problem: Solve the Tower of Hanoi problem for 3 disks.

#include <stdio.h>

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int n = 3; // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
    return 0;
}

3. Print All Subsequences of a String

Problem: Implement a recursive program to print all subsequences of a string.

#include <stdio.h>
#include <string.h>

void printSubsequences(char *str, char *output, int index) {
    if (str[index] == '\0') {
        output[index] = '\0';
        printf("%s\n", output);
        return;
    }
    output[index] = str[index];
    printSubsequences(str, output, index + 1);
    printSubsequences(str, output, index + 1);
}

int main() {
    char str[] = "abc";
    char output[strlen(str) + 1];
    printSubsequences(str, output, 0);
    return 0;
}

4. Find the nth Fibonacci Number

Problem: Write a recursive function to find the nth Fibonacci number.

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int n = 10;
    printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));
    return 0;
}

5. Sum of Digits in a Number

Problem: Solve the "sum of digits in a number" problem using recursion.

#include <stdio.h>

int sumOfDigits(int n) {
    if (n == 0) {
        return 0;
    } else {
        return (n % 10) + sumOfDigits(n / 10);
    }
}

int main() {
    int number = 1234;
    printf("Sum of digits in %d is %d\n", number, sumOfDigits(number));
    return 0;
}

Conclusion

That wraps up Day 7 of our DSA challenge! We explored some fundamental recursion problems and implemented solutions in C language. Recursion is a powerful concept that can simplify complex problems by breaking them down into smaller, manageable parts. Keep practicing, and you'll become more comfortable with recursive thinking.

Stay tuned for more exciting problems and solutions as we continue to improve our skills in data structures and algorithms.