Welcome to Day 7 of my 100 Days of DSA challenge! 🚀 Today, I dove into the fascinating world of recursion, solving five engaging problems that tested my understanding of this core concept. Recursion is a powerful tool that simplifies complex problems by breaking them down into smaller, more manageable parts.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Excited to share what I learned and continue building my skills! ✨
1. Factorial of a Number Using a Recursive Function
This program calculates the factorial of a number using recursion. The function recur_factorial repeatedly calls itself with a decremented value of n until it reaches the base case (n == 0), where it returns 1.
Code:
#include <iostream>
using namespace std;
// Recursive function to calculate factorial
int recur_factorial(int n) {
// Base case: factorial of 0 is 1
if (n == 0) {
return 1;
}
else {
// Recursive step: n * factorial of (n-1)
return n * recur_factorial(n - 1);
}
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
int factorial = recur_factorial(n);
cout << "The factorial of given number, " << n << ", is " << factorial << ".";
return 0;
}
Output:
2. Tower of Hanoi Problem for 3 Disks
The Tower of Hanoi problem involves moving a set of disks from a source rod to a destination rod using an auxiliary rod, following these rules:
Only one disk can be moved at a time
A larger disk cannot be placed on top of a smaller disk
And only the top disk of a rod can be moved
The solution is recursive: move n−1 disks from the source to the auxiliary rod, then move the largest disk to the destination, and finally move the n−1 disks from the auxiliary to the destination.
In the code, the tower_of_hanoi function implements this recursive logic. For each recursive step, the function moves smaller disks first, then the largest disk, and finally the smaller disks to their target position. The base case is when there is only one disk to move, which is handled directly.
Code:
#include <iostream>
using namespace std;
// Recursive function to solve Tower of Hanoi
void tower_of_hanoi(int n, char src, char dest, char aux) {
// Base case: If there's only one disk, move it directly
if (n == 1) {
cout << "Move disk number 1 from " << src << " to " << dest << endl;
return;
}
// Step 1: Move n-1 disks from source to auxiliary using destination as auxiliary
tower_of_hanoi(n - 1, src, aux, dest);
// Step 2: Move the nth disk from source to destination
cout << "Move disk number " << n << " from " << src << " to " << dest << endl;
// Step 3: Move the n-1 disks from auxiliary to destination using source as auxiliary
tower_of_hanoi(n - 1, aux, dest, src);
}
int main() {
int n = 3;
cout << "Steps to solve the Tower of Hanoi for " << n << " disks are as follows:" << endl;
tower_of_hanoi(n, 'A', 'C', 'B'); // A = source, C = destination, B = auxiliary
return 0;
}
Output:
3. Subsequences of a String Using a Recursive Function
This program generates and prints all subsequences of a given string using recursion. At each step, it either includes or excludes the current character from the subsequence being formed. This process continues recursively until the input string becomes empty, at which point the constructed subsequence is printed. The function explores all possible combinations of characters, effectively generating every subsequence.
Code:
#include <iostream>
using namespace std;
// Recursive function to print all subsequences of the string
void print_subsequences(string input, string output) {
// Base case: If the input is empty, print the output
if (input.empty()) {
cout << output << endl;
return;
}
// Include the first character of the input in the output
print_subsequences(input.substr(1), output + input[0]);
// Exclude the first character of the input from the output
print_subsequences(input.substr(1), output);
}
int main() {
string str;
cout << "Enter a string: ";
cin >> str;
cout << "All subsequences of the string are: " << endl;
print_subsequences(str, "");
return 0;
}
Output:
4. Nth Fibonacci Number Using a Recursive Function
The code calculates the nth Fibonacci number using recursion. It defines a base case where the 0th Fibonacci number is 0 and the 1st Fibonacci number is 1. For larger n, the function calls itself to compute the sum of the (n−1)th and (n−2)th Fibonacci numbers. The main function takes user input for n and prints the result.
Code:
#include <iostream>
using namespace std;
// Recursive function to find the nth Fibonacci number
int recur_fibonacci(int n) {
// Base cases: Fibonacci(0) = 0, Fibonacci(1) = 1
if (n == 1 || n == 0) {
return n;
}
else {
// Recursive step: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
return recur_fibonacci(n - 1) + recur_fibonacci(n - 2);
}
}
int main() {
int n;
cout << "Enter the position of the Fibonacci number: ";
cin >> n;
int result = recur_fibonacci(n);
cout << "The " << n << "th Fibonacci number is: " << result << endl;
return 0;
}
Output:
5. Sum of Digits in a Number Using a Recursion Function
This program calculates the sum of the digits of a number using recursion. It repeatedly adds the last digit of the number (n % 10) to the sum of the digits of the remaining number (n / 10) until the number becomes zero, which is the base case. Negative numbers are converted to positive before the calculation.
Code:
#include <iostream>
using namespace std;
// Recursive function to find the sum of digits of a number
int sum_of_digits(int n) {
// Base case: If the number is 0, the sum is 0
if (n == 0) {
return 0;
}
else {
// Recursive step: Add the last digit to the sum of the remaining digits
return n % 10 + sum_of_digits(n / 10);
}
}
int main() {
int n;
cout << "Enter a number: ";
cin >> n;
// Handle negative numbers by converting to positive
if (n < 0) {
n = -n;
}
int result = sum_of_digits(n);
cout << "The sum of the digits of the number is: " << result;
return 0;
}
Output:
Day 7 was all about diving deep into recursion, a technique that simplifies problem-solving by breaking tasks into smaller, manageable steps. While it can be tricky to ensure proper base cases and termination conditions, it’s an essential skill for efficient algorithm design.
Excited to see what new challenges Day 8 will bring! 🚀