WikiGalaxy
C++ Recursion
Understanding Recursion:
Recursion is a programming technique where a function calls itself in order to solve a problem. This approach is useful for problems that can be broken down into smaller, similar problems.
Base Case and Recursive Case:
Every recursive function must have a base case, which stops the recursion, and a recursive case, which continues the recursion.
#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0) return 1; // Base case
return n * factorial(n - 1); // Recursive case
}
int main() {
cout << "Factorial of 5 is " << factorial(5) << endl;
return 0;
}
Console Output:
Factorial of 5 is 120
Fibonacci Sequence
Recursive Fibonacci:
The Fibonacci sequence is a classic example of recursion, where each term is the sum of the two preceding ones.
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n; // Base case
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
int main() {
cout << "Fibonacci of 5 is " << fibonacci(5) << endl;
return 0;
}
Console Output:
Fibonacci of 5 is 5
Sum of Digits
Recursive Sum:
Calculate the sum of digits of a number using recursion by breaking down the number into its last digit and the rest.
#include <iostream>
using namespace std;
int sumOfDigits(int n) {
if (n == 0) return 0; // Base case
return (n % 10) + sumOfDigits(n / 10); // Recursive case
}
int main() {
cout << "Sum of digits of 123 is " << sumOfDigits(123) << endl;
return 0;
}
Console Output:
Sum of digits of 123 is 6
Power of a Number
Recursive Power:
Compute the power of a number using recursion by multiplying the base with the result of the power function with a reduced exponent.
#include <iostream>
using namespace std;
int power(int base, int exp) {
if (exp == 0) return 1; // Base case
return base * power(base, exp - 1); // Recursive case
}
int main() {
cout << "2 raised to the power 3 is " << power(2, 3) << endl;
return 0;
}
Console Output:
2 raised to the power 3 is 8
Greatest Common Divisor (GCD)
Recursive GCD:
Find the GCD of two numbers using the Euclidean algorithm recursively, which involves repeated division.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a; // Base case
return gcd(b, a % b); // Recursive case
}
int main() {
cout << "GCD of 48 and 18 is " << gcd(48, 18) << endl;
return 0;
}
Console Output:
GCD of 48 and 18 is 6
Binary Search
Recursive Binary Search:
Binary search is an efficient algorithm for finding an item from a sorted list of items, using a divide-and-conquer approach.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) return mid; // Base case
if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Recursive case
return binarySearch(arr, mid + 1, r, x); // Recursive case
}
return -1; // Element not found
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
cout << "Element found at index " << result << endl;
return 0;
}
Console Output:
Element found at index 3
Reverse a String
Recursive String Reversal:
Reverse a string using recursion by reducing the problem size and appending characters in reverse order.
#include <iostream>
using namespace std;
void reverseString(string &str, int start, int end) {
if (start >= end) return; // Base case
swap(str[start], str[end]);
reverseString(str, start + 1, end - 1); // Recursive case
}
int main() {
string str = "Hello";
reverseString(str, 0, str.length() - 1);
cout << "Reversed string is " << str << endl;
return 0;
}
Console Output:
Reversed string is olleH
Tower of Hanoi
Recursive Tower of Hanoi:
Solve the Tower of Hanoi problem using recursion by moving disks between rods according to the rules.
#include <iostream>
using namespace std;
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;
return; // Base case
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); // Recursive case
cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); // Recursive case
}
int main() {
int n = 3; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}
Console Output:
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
Permutations of a String
Recursive Permutations:
Generate all permutations of a string using recursion by swapping characters and reducing the problem size.
#include <iostream>
#include <string>
using namespace std;
void permute(string str, int l, int r) {
if (l == r)
cout << str << endl; // Base case
else {
for (int i = l; i <= r; i++) {
swap(str[l], str[i]);
permute(str, l + 1, r); // Recursive case
swap(str[l], str[i]); // backtrack
}
}
}
int main() {
string str = "ABC";
permute(str, 0, str.size() - 1);
return 0;
}
Console Output:
ABC
ACB
BAC
BCA
CBA
CAB
