Table of contents
- Q1. Write a recursive function to calculate the factorial of a number.
- Q2. Solve the Tower of Hanoi problem for 3 disks.
- Q3. Implement a recursive program to print all subsequences of a string.
- Q4. Write a recursive function to find the nth Fibonacci number.
- Q5. Solve the "sum of digits in a number" problem using recursion.
Today’s practice was all about recursion basics. I tackled problems like calculating the factorial of a number recursively, solving the Tower of Hanoi problem for 3 disks, and implementing a program to print all subsequences of a string using recursion. Additionally, I worked on finding the nth Fibonacci number and calculating the sum of digits of a number recursively. These exercises helped me solidify my understanding of recursion and its various applications.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Write a recursive function to calculate the factorial of a number.
#include <iostream>
using namespace std;
int factorial(int n){;
if(n<=0){
return 1;
}
else
return n*factorial(n-1);
}
int main()
{
int n;
cout<<"Enter no to print factorial of: ";
cin>>n;
cout<<factorial(n);
return 0;
}
The given program calculates the factorial of a number using recursion. The function factorial(int n) works by repeatedly calling itself with a decrementing value of n until it reaches the base case where n <= 0. In the base case, the function returns 1 because the factorial of 0 or a negative number is defined as 1. Otherwise, the function multiplies the current value of n by the result of factorial(n-1), which essentially reduces the problem until it reaches the base case.
Q2. Solve the Tower of Hanoi problem for 3 disks.
#include <iostream>
using namespace std;
void Tower_of_Hanoi(int n,int A, int B, int C){
if(n>0){
Tower_of_Hanoi(n-1,A,C,B);
cout<<"Move a disk from "<<A<<" to "<<C<<endl;
Tower_of_Hanoi(n-1,B,A,C);
}
}
int main()
{ int n=3;
Tower_of_Hanoi(n,1,2,3);
return 0;
}
The program solves the Tower of Hanoi problem for 3 disks using recursion. It works by breaking down the problem into smaller subproblems: moving n-1 disks from the source rod to the auxiliary rod, moving the largest disk to the destination rod, and then moving the n-1 disks from the auxiliary rod to the destination rod. The Tower_of_Hanoi function is called recursively to handle each step. In the main() function, Tower_of_Hanoi(3, 1, 2, 3) is used to move 3 disks from rod 1 (source) to rod 3 (destination) using rod 2 as the auxiliary. The program prints the steps to move each disk from one rod to another.
Q3. Implement a recursive program to print all subsequences of a string.
#include <iostream>
using namespace std;
void generate_subsequence(string str, string curr, int i) {
if (i == str.size()) {
cout << curr << endl;
return;
}
generate_subsequence(str,curr,i+1); // Exclude the current character and proceed
generate_subsequence(str,curr+str[i],i+1); // Include the current character and proceed
}
int main() {
string str;
cout << "Enter string: ";
getline(cin, str);
generate_subsequence(str, "", 0);
return 0;
}
This program generates all possible subsequences of a given string using recursion. The generate_subsequence function takes the string str, a curr string (representing the current subsequence), and an index i. It explores both possibilities for each character: either excluding it or including it in the subsequence. When the index reaches the end of the string, the function prints the current subsequence. The main() function reads the input string and starts the recursion by calling generate_subsequence with an empty string and starting index 0. The result is the complete set of subsequences.
Q4. Write a recursive function to find the nth Fibonacci number.
#include <iostream>
using namespace std;
int fibonacci(int n){
if(n==0||n==1){
return n;
}
else
return fibonacci(n-1)+fibonacci(n-2);
}
int main()
{ int n;
cout<<"Enter which number of the sequence you want to find: ";
cin>>n;
cout << "Fibonacci at "<<n<<" position: ";
cout<<fibonacci(n);
return 0;
}
This program calculates the nth Fibonacci number using recursion. The fibonacci function checks if the input n is 0 or 1, in which case it returns n directly, as these are the base cases for the Fibonacci sequence. For other values of n, the function recursively calls itself to compute the sum of the Fibonacci numbers at positions n-1 and n-2. The main() function reads the value of n from the user and calls the fibonacci function to print the nth Fibonacci number. This approach follows the direct definition of the Fibonacci sequence.
Q5. Solve the "sum of digits in a number" problem using recursion.
#include <iostream>
using namespace std;
int sum_of_digits(int n,int sum){
if(n==0){
return sum;
}
sum=sum+n%10;
n=(n-n%10)/10;
return sum_of_digits(n,sum);
}
int main()
{
int n;
cout<<"Enter the number: ";
cin>>n;
int sum=0;
cout<<sum_of_digits(n,sum);
return 0;
}
This program calculates the sum of digits of a given number using recursion. The sum_of_digits function takes two parameters: the number n and an accumulator sum. It recursively extracts the last digit of n by using the modulo operator (n % 10) and adds it to the accumulator. Then, it removes the last digit of n by dividing it by 10. The base case occurs when n becomes 0, at which point the accumulated sum is returned. The main() function reads the input number, initializes the sum as 0, and calls the recursive function to compute and print the result.
Today’s practice deepened my understanding of recursion. From calculating factorials and Fibonacci numbers to solving the Tower of Hanoi and printing subsequences, each problem enhanced my problem-solving approach. Recursion is a powerful tool for solving many complex problems, and I’m excited to continue refining my skills with more advanced challenges. Onward to Day 8!