cpp
examples
examples.cpp⚙️cpp
/**
* Recursion in C++ - Comprehensive Examples
*
* Demonstrates:
* - Basic recursive functions
* - Classic recursive problems
* - Recursion on data structures
* - Backtracking
* - Tail recursion
* - Memoization
*
* Compile: g++ -std=c++17 -Wall -Wextra examples.cpp -o examples
* Run: ./examples
*/
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;
// ============================================================
// SECTION 1: BASIC RECURSION
// ============================================================
/**
* Countdown from n to 0
*/
void countdown(int n) {
if (n <= 0) {
cout << "Liftoff!" << endl;
return;
}
cout << n << "... ";
countdown(n - 1);
}
/**
* Print numbers from 1 to n (demonstrating recursion before print)
*/
void countUp(int n) {
if (n <= 0) return;
countUp(n - 1); // Recurse first
cout << n << " "; // Print after returning
}
/**
* Calculate factorial: n! = n × (n-1) × ... × 1
*/
long long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
/**
* Calculate power: base^exp
*/
double power(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / power(base, -exp);
return base * power(base, exp - 1);
}
/**
* Efficient power using divide and conquer: O(log n)
*/
double powerFast(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / powerFast(base, -exp);
if (exp % 2 == 0) {
double half = powerFast(base, exp / 2);
return half * half;
} else {
return base * powerFast(base, exp - 1);
}
}
// ============================================================
// SECTION 2: MATHEMATICAL RECURSION
// ============================================================
/**
* Fibonacci number (naive recursive)
*/
int fibonacciNaive(int n) {
if (n <= 1) return n;
return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}
/**
* Fibonacci with memoization
*/
unordered_map<int, long long> fibMemo;
long long fibonacciMemo(int n) {
if (n <= 1) return n;
if (fibMemo.count(n)) return fibMemo[n];
fibMemo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
return fibMemo[n];
}
/**
* Sum of digits
*/
int sumDigits(int n) {
n = abs(n); // Handle negative
if (n < 10) return n;
return (n % 10) + sumDigits(n / 10);
}
/**
* Count digits
*/
int countDigits(int n) {
n = abs(n);
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
/**
* GCD using Euclidean algorithm
*/
int gcd(int a, int b) {
if (b == 0) return abs(a);
return gcd(b, a % b);
}
/**
* LCM using GCD
*/
int lcm(int a, int b) {
return abs(a * b) / gcd(a, b);
}
// ============================================================
// SECTION 3: STRING RECURSION
// ============================================================
/**
* Reverse a string
*/
string reverseString(const string& s) {
if (s.length() <= 1) return s;
return reverseString(s.substr(1)) + s[0];
}
/**
* Check if string is palindrome
*/
bool isPalindrome(const string& s, int left, int right) {
if (left >= right) return true;
if (s[left] != s[right]) return false;
return isPalindrome(s, left + 1, right - 1);
}
bool isPalindrome(const string& s) {
return isPalindrome(s, 0, s.length() - 1);
}
/**
* Count character occurrences
*/
int countChar(const string& s, char c, int index = 0) {
if (index >= (int)s.length()) return 0;
int count = (s[index] == c) ? 1 : 0;
return count + countChar(s, c, index + 1);
}
/**
* Remove all occurrences of a character
*/
string removeChar(const string& s, char c) {
if (s.empty()) return "";
string rest = removeChar(s.substr(1), c);
if (s[0] == c) return rest;
return s[0] + rest;
}
// ============================================================
// SECTION 4: ARRAY/VECTOR RECURSION
// ============================================================
/**
* Sum of array elements
*/
int sumArray(const vector<int>& arr, int index = 0) {
if (index >= (int)arr.size()) return 0;
return arr[index] + sumArray(arr, index + 1);
}
/**
* Find maximum element
*/
int maxElement(const vector<int>& arr, int index = 0) {
if (index == (int)arr.size() - 1) return arr[index];
return max(arr[index], maxElement(arr, index + 1));
}
/**
* Check if array is sorted
*/
bool isSorted(const vector<int>& arr, int index = 0) {
if (index >= (int)arr.size() - 1) return true;
if (arr[index] > arr[index + 1]) return false;
return isSorted(arr, index + 1);
}
/**
* Binary search (recursive)
*/
int binarySearch(const vector<int>& arr, int target, int low, int high) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] > target) return binarySearch(arr, target, low, mid - 1);
return binarySearch(arr, target, mid + 1, high);
}
int binarySearch(const vector<int>& arr, int target) {
return binarySearch(arr, target, 0, arr.size() - 1);
}
// ============================================================
// SECTION 5: BACKTRACKING EXAMPLES
// ============================================================
/**
* Generate all subsets of a vector
*/
void generateSubsets(const vector<int>& arr, int index,
vector<int>& current, vector<vector<int>>& result) {
if (index == (int)arr.size()) {
result.push_back(current);
return;
}
// Include current element
current.push_back(arr[index]);
generateSubsets(arr, index + 1, current, result);
// Exclude current element (backtrack)
current.pop_back();
generateSubsets(arr, index + 1, current, result);
}
vector<vector<int>> getSubsets(const vector<int>& arr) {
vector<vector<int>> result;
vector<int> current;
generateSubsets(arr, 0, current, result);
return result;
}
/**
* Generate all permutations of a string
*/
void generatePermutations(string& s, int start, vector<string>& result) {
if (start == (int)s.length()) {
result.push_back(s);
return;
}
for (int i = start; i < (int)s.length(); i++) {
swap(s[start], s[i]);
generatePermutations(s, start + 1, result);
swap(s[start], s[i]); // Backtrack
}
}
vector<string> getPermutations(string s) {
vector<string> result;
generatePermutations(s, 0, result);
return result;
}
// ============================================================
// SECTION 6: DIVIDE AND CONQUER
// ============================================================
/**
* Merge sort helper: merge two sorted halves
*/
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i++]);
} else {
temp.push_back(arr[j++]);
}
}
while (i <= mid) temp.push_back(arr[i++]);
while (j <= right) temp.push_back(arr[j++]);
for (int k = 0; k < (int)temp.size(); k++) {
arr[left + k] = temp[k];
}
}
/**
* Merge sort (recursive)
*/
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void mergeSort(vector<int>& arr) {
if (arr.size() > 1) {
mergeSort(arr, 0, arr.size() - 1);
}
}
// ============================================================
// SECTION 7: TAIL RECURSION
// ============================================================
/**
* Factorial with tail recursion
*/
long long factorialTail(int n, long long acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc);
}
/**
* Sum with tail recursion
*/
int sumTail(const vector<int>& arr, int index = 0, int acc = 0) {
if (index >= (int)arr.size()) return acc;
return sumTail(arr, index + 1, acc + arr[index]);
}
/**
* Fibonacci with tail recursion
*/
long long fibTail(int n, long long a = 0, long long b = 1) {
if (n == 0) return a;
if (n == 1) return b;
return fibTail(n - 1, b, a + b);
}
// ============================================================
// SECTION 8: TREE RECURSION (SIMULATED)
// ============================================================
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : value(v), left(nullptr), right(nullptr) {}
};
/**
* Calculate tree height
*/
int treeHeight(TreeNode* root) {
if (root == nullptr) return 0;
return 1 + max(treeHeight(root->left), treeHeight(root->right));
}
/**
* Sum of all tree values
*/
int treeSum(TreeNode* root) {
if (root == nullptr) return 0;
return root->value + treeSum(root->left) + treeSum(root->right);
}
/**
* Count nodes in tree
*/
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
/**
* Inorder traversal
*/
void inorder(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
inorder(root->left, result);
result.push_back(root->value);
inorder(root->right, result);
}
// ============================================================
// DEMONSTRATION FUNCTIONS
// ============================================================
void demonstrateBasicRecursion() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 1: Basic Recursion ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
cout << "Countdown from 5: ";
countdown(5);
cout << "Count up to 5: ";
countUp(5);
cout << endl;
cout << "Factorial(5) = " << factorial(5) << endl;
cout << "Factorial(10) = " << factorial(10) << endl;
cout << "power(2, 10) = " << power(2, 10) << endl;
cout << "power(2, -3) = " << power(2, -3) << endl;
cout << "powerFast(2, 10) = " << powerFast(2, 10) << endl;
}
void demonstrateMathematicalRecursion() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 2: Mathematical Recursion ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
cout << "Fibonacci (first 15): ";
for (int i = 0; i < 15; i++) {
cout << fibonacciMemo(i) << " ";
}
cout << endl;
cout << "sumDigits(12345) = " << sumDigits(12345) << endl;
cout << "countDigits(12345) = " << countDigits(12345) << endl;
cout << "gcd(48, 18) = " << gcd(48, 18) << endl;
cout << "lcm(4, 6) = " << lcm(4, 6) << endl;
}
void demonstrateStringRecursion() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 3: String Recursion ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
cout << "reverseString(\"hello\") = " << reverseString("hello") << endl;
cout << "isPalindrome(\"radar\") = " << boolalpha << isPalindrome("radar") << endl;
cout << "isPalindrome(\"hello\") = " << isPalindrome("hello") << endl;
cout << "countChar(\"mississippi\", 's') = " << countChar("mississippi", 's') << endl;
cout << "removeChar(\"hello\", 'l') = " << removeChar("hello", 'l') << endl;
}
void demonstrateArrayRecursion() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 4: Array/Vector Recursion ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
cout << "Array: [";
for (size_t i = 0; i < arr.size(); i++) {
cout << arr[i] << (i < arr.size()-1 ? ", " : "");
}
cout << "]" << endl;
cout << "sumArray = " << sumArray(arr) << endl;
cout << "maxElement = " << maxElement(arr) << endl;
cout << "isSorted = " << boolalpha << isSorted(arr) << endl;
vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << "binarySearch(sorted, 5) = " << binarySearch(sorted, 5) << endl;
cout << "binarySearch(sorted, 10) = " << binarySearch(sorted, 10) << endl;
}
void demonstrateBacktracking() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 5: Backtracking ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
cout << "Subsets of {1, 2, 3}:" << endl;
vector<int> nums = {1, 2, 3};
auto subsets = getSubsets(nums);
for (const auto& subset : subsets) {
cout << " {";
for (size_t i = 0; i < subset.size(); i++) {
cout << subset[i] << (i < subset.size()-1 ? ", " : "");
}
cout << "}" << endl;
}
cout << "\nPermutations of \"ABC\":" << endl;
auto perms = getPermutations("ABC");
cout << " ";
for (size_t i = 0; i < perms.size(); i++) {
cout << perms[i] << (i < perms.size()-1 ? ", " : "");
}
cout << endl;
}
void demonstrateDivideAndConquer() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 6: Divide and Conquer ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
cout << "Original: [";
for (size_t i = 0; i < arr.size(); i++) {
cout << arr[i] << (i < arr.size()-1 ? ", " : "");
}
cout << "]" << endl;
mergeSort(arr);
cout << "After merge sort: [";
for (size_t i = 0; i < arr.size(); i++) {
cout << arr[i] << (i < arr.size()-1 ? ", " : "");
}
cout << "]" << endl;
}
void demonstrateTailRecursion() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 7: Tail Recursion ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
cout << "factorialTail(10) = " << factorialTail(10) << endl;
vector<int> arr = {1, 2, 3, 4, 5};
cout << "sumTail({1,2,3,4,5}) = " << sumTail(arr) << endl;
cout << "fibTail(40) = " << fibTail(40) << " (fast!)" << endl;
}
void demonstrateTreeRecursion() {
cout << "\n╔══════════════════════════════════════════════════════════════╗" << endl;
cout << "║ SECTION 8: Tree Recursion ║" << endl;
cout << "╚══════════════════════════════════════════════════════════════╝" << endl;
// Build a simple tree:
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << "Tree structure:" << endl;
cout << " 1" << endl;
cout << " / \\" << endl;
cout << " 2 3" << endl;
cout << " / \\" << endl;
cout << " 4 5" << endl;
cout << "Height: " << treeHeight(root) << endl;
cout << "Sum: " << treeSum(root) << endl;
cout << "Node count: " << countNodes(root) << endl;
vector<int> inorderResult;
inorder(root, inorderResult);
cout << "Inorder traversal: ";
for (int n : inorderResult) cout << n << " ";
cout << endl;
// Cleanup
delete root->left->left;
delete root->left->right;
delete root->left;
delete root->right;
delete root;
}
// ============================================================
// MAIN FUNCTION
// ============================================================
int main() {
cout << "╔════════════════════════════════════════════════════════════════════╗" << endl;
cout << "║ C++ RECURSION EXAMPLES ║" << endl;
cout << "║ Functions That Call Themselves ║" << endl;
cout << "╚════════════════════════════════════════════════════════════════════╝" << endl;
demonstrateBasicRecursion();
demonstrateMathematicalRecursion();
demonstrateStringRecursion();
demonstrateArrayRecursion();
demonstrateBacktracking();
demonstrateDivideAndConquer();
demonstrateTailRecursion();
demonstrateTreeRecursion();
cout << "\n╔════════════════════════════════════════════════════════════════════╗" << endl;
cout << "║ Examples Complete! ║" << endl;
cout << "╚════════════════════════════════════════════════════════════════════╝" << endl;
return 0;
}