cpp
Recursion
04_Recursion⚙️cpp
/**
* ============================================================
* C++ RECURSION
* ============================================================
*
* This file covers:
* - What is recursion
* - Base case and recursive case
* - Common recursive patterns
* - Recursion vs iteration
* - Tail recursion
*
* Compile: g++ -std=c++17 -Wall 01_recursion.cpp -o recursion
* Run: ./recursion
*
* ============================================================
*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// ============================================================
// FUNCTION DECLARATIONS
// ============================================================
// Basic recursion examples
int factorial(int n);
int fibonacci(int n);
int sum(int n);
// Array/string recursion
int sumArray(int arr[], int size);
void printReverse(const string& str, int index);
bool isPalindrome(const string& str, int start, int end);
// Mathematical recursion
int power(int base, int exp);
int gcd(int a, int b);
// Visual recursion
void printPattern(int n);
void printTriangle(int n);
void countdown(int n);
// Advanced examples
int binarySearch(int arr[], int left, int right, int target);
void hanoi(int n, char from, char to, char aux);
// ============================================================
// MAIN FUNCTION
// ============================================================
int main() {
cout << "============================================" << endl;
cout << " C++ RECURSION" << endl;
cout << "============================================" << endl << endl;
// ========================================================
// PART 1: UNDERSTANDING RECURSION
// ========================================================
cout << "--- PART 1: UNDERSTANDING RECURSION ---" << endl << endl;
/*
* RECURSION: A function that calls itself
*
* Key Components:
* 1. BASE CASE: Condition to stop recursion
* 2. RECURSIVE CASE: Function calls itself with modified input
*
* Without a base case → INFINITE RECURSION → STACK OVERFLOW!
*/
cout << "Recursion = Base Case + Recursive Case" << endl;
cout << endl;
cout << "Example: factorial(5)" << endl;
cout << " factorial(5) = 5 * factorial(4)" << endl;
cout << " factorial(4) = 4 * factorial(3)" << endl;
cout << " factorial(3) = 3 * factorial(2)" << endl;
cout << " factorial(2) = 2 * factorial(1)" << endl;
cout << " factorial(1) = 1 ← BASE CASE!" << endl;
cout << " Then it unwinds: 1→2→6→24→120" << endl;
cout << endl;
// ========================================================
// PART 2: FACTORIAL
// ========================================================
cout << "--- PART 2: FACTORIAL ---" << endl << endl;
cout << "factorial(0) = " << factorial(0) << endl;
cout << "factorial(1) = " << factorial(1) << endl;
cout << "factorial(5) = " << factorial(5) << endl;
cout << "factorial(10) = " << factorial(10) << endl;
cout << endl;
// ========================================================
// PART 3: FIBONACCI
// ========================================================
cout << "--- PART 3: FIBONACCI ---" << endl << endl;
cout << "Fibonacci sequence: ";
for (int i = 0; i < 15; i++) {
cout << fibonacci(i) << " ";
}
cout << endl;
// Note: This naive implementation is inefficient (exponential time)
// For large n, use dynamic programming or iteration
cout << endl;
// ========================================================
// PART 4: SUM OF NUMBERS
// ========================================================
cout << "--- PART 4: SUM OF NUMBERS ---" << endl << endl;
cout << "sum(5) = 1+2+3+4+5 = " << sum(5) << endl;
cout << "sum(10) = " << sum(10) << endl;
cout << "sum(100) = " << sum(100) << endl;
cout << endl;
// ========================================================
// PART 5: ARRAY RECURSION
// ========================================================
cout << "--- PART 5: ARRAY RECURSION ---" << endl << endl;
int arr[] = {1, 2, 3, 4, 5};
int arrSize = 5;
cout << "Array: [1, 2, 3, 4, 5]" << endl;
cout << "Sum of array: " << sumArray(arr, arrSize) << endl;
cout << endl;
// ========================================================
// PART 6: STRING RECURSION
// ========================================================
cout << "--- PART 6: STRING RECURSION ---" << endl << endl;
string str = "Hello";
cout << "Original: " << str << endl;
cout << "Reversed: ";
printReverse(str, str.length() - 1);
cout << endl;
// Palindrome check
cout << "\nPalindrome check:" << endl;
string test1 = "racecar";
string test2 = "hello";
string test3 = "madam";
cout << "\"" << test1 << "\" is palindrome: "
<< (isPalindrome(test1, 0, test1.length()-1) ? "Yes" : "No") << endl;
cout << "\"" << test2 << "\" is palindrome: "
<< (isPalindrome(test2, 0, test2.length()-1) ? "Yes" : "No") << endl;
cout << "\"" << test3 << "\" is palindrome: "
<< (isPalindrome(test3, 0, test3.length()-1) ? "Yes" : "No") << endl;
cout << endl;
// ========================================================
// PART 7: MATHEMATICAL RECURSION
// ========================================================
cout << "--- PART 7: MATH RECURSION ---" << endl << endl;
cout << "power(2, 10) = " << power(2, 10) << endl;
cout << "power(3, 4) = " << power(3, 4) << endl;
cout << "\nGCD (Euclidean algorithm):" << endl;
cout << "gcd(48, 18) = " << gcd(48, 18) << endl;
cout << "gcd(56, 98) = " << gcd(56, 98) << endl;
cout << endl;
// ========================================================
// PART 8: VISUAL PATTERNS
// ========================================================
cout << "--- PART 8: VISUAL PATTERNS ---" << endl << endl;
cout << "Countdown from 5:" << endl;
countdown(5);
cout << "\nTriangle pattern (n=5):" << endl;
printTriangle(5);
cout << "\nStar pattern (n=4):" << endl;
printPattern(4);
cout << endl;
// ========================================================
// PART 9: BINARY SEARCH (RECURSIVE)
// ========================================================
cout << "--- PART 9: BINARY SEARCH ---" << endl << endl;
int sortedArr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = 10;
cout << "Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]" << endl;
int target = 23;
int result = binarySearch(sortedArr, 0, size-1, target);
cout << "Search for " << target << ": "
<< (result != -1 ? "Found at index " + to_string(result) : "Not found") << endl;
target = 100;
result = binarySearch(sortedArr, 0, size-1, target);
cout << "Search for " << target << ": "
<< (result != -1 ? "Found at index " + to_string(result) : "Not found") << endl;
cout << endl;
// ========================================================
// PART 10: TOWER OF HANOI
// ========================================================
cout << "--- PART 10: TOWER OF HANOI ---" << endl << endl;
cout << "Tower of Hanoi with 3 disks:" << endl;
cout << "(Move all disks from A to C using B as auxiliary)" << endl;
cout << endl;
hanoi(3, 'A', 'C', 'B');
cout << endl;
// ========================================================
// PART 11: RECURSION VS ITERATION
// ========================================================
cout << "--- PART 11: RECURSION VS ITERATION ---" << endl << endl;
cout << "┌─────────────────┬─────────────────┬─────────────────┐" << endl;
cout << "│ Aspect │ Recursion │ Iteration │" << endl;
cout << "├─────────────────┼─────────────────┼─────────────────┤" << endl;
cout << "│ Memory │ Uses stack │ Constant space │" << endl;
cout << "│ Speed │ Overhead │ Usually faster │" << endl;
cout << "│ Readability │ Often cleaner │ Can be complex │" << endl;
cout << "│ Stack overflow │ Possible │ No │" << endl;
cout << "│ Best for │ Trees, divide& │ Simple loops │" << endl;
cout << "│ │ conquer │ │" << endl;
cout << "└─────────────────┴─────────────────┴─────────────────┘" << endl;
cout << "\n💡 When to use recursion:" << endl;
cout << "• Tree/graph traversal" << endl;
cout << "• Divide and conquer algorithms" << endl;
cout << "• Problems naturally defined recursively" << endl;
cout << "• When code clarity is important" << endl;
cout << endl;
cout << "============================================" << endl;
cout << "RECURSION SUMMARY:" << endl;
cout << "============================================" << endl;
cout << "• Function calls itself" << endl;
cout << "• Must have base case to stop" << endl;
cout << "• Each call adds to call stack" << endl;
cout << "• Elegant for tree/graph problems" << endl;
cout << "• Watch for stack overflow" << endl;
cout << "============================================" << endl;
return 0;
}
// ============================================================
// FUNCTION DEFINITIONS
// ============================================================
/*
* Factorial: n! = n * (n-1) * (n-2) * ... * 1
* Base case: 0! = 1! = 1
*/
int factorial(int n) {
// Base case
if (n <= 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
/*
* Fibonacci: F(n) = F(n-1) + F(n-2)
* Base cases: F(0) = 0, F(1) = 1
*/
int fibonacci(int n) {
// Base cases
if (n == 0) return 0;
if (n == 1) return 1;
// Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}
/*
* Sum of 1 to n
* Base case: sum(0) = 0
*/
int sum(int n) {
if (n <= 0) return 0;
return n + sum(n - 1);
}
/*
* Sum of array elements
* Base case: size == 0
*/
int sumArray(int arr[], int size) {
if (size <= 0) return 0;
return arr[size - 1] + sumArray(arr, size - 1);
}
/*
* Print string in reverse
*/
void printReverse(const string& str, int index) {
if (index < 0) return; // Base case
cout << str[index];
printReverse(str, index - 1); // Recursive case
}
/*
* Check if string is palindrome
*/
bool isPalindrome(const string& str, int start, int end) {
// Base case: checked all characters
if (start >= end) return true;
// If characters don't match
if (str[start] != str[end]) return false;
// Check inner substring
return isPalindrome(str, start + 1, end - 1);
}
/*
* Power: base^exp
* Base case: exp == 0 returns 1
*/
int power(int base, int exp) {
if (exp == 0) return 1;
return base * power(base, exp - 1);
}
/*
* GCD using Euclidean algorithm
* gcd(a, b) = gcd(b, a % b)
* Base case: b == 0 returns a
*/
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
/*
* Print countdown
*/
void countdown(int n) {
if (n < 0) return; // Base case
cout << n << " ";
countdown(n - 1); // Recursive case
}
/*
* Print triangle pattern
*/
void printTriangle(int n) {
if (n <= 0) return; // Base case
printTriangle(n - 1); // Print smaller triangle first
for (int i = 0; i < n; i++) {
cout << "* ";
}
cout << endl;
}
/*
* Print pattern - stars going up then down
*/
void printPattern(int n) {
if (n <= 0) return;
// Print stars
for (int i = 0; i < n; i++) {
cout << "*";
}
cout << endl;
printPattern(n - 1); // Recurse with smaller n
// Print stars again (after recursion returns)
for (int i = 0; i < n; i++) {
cout << "*";
}
cout << endl;
}
/*
* Binary search (recursive)
* Returns index of target, or -1 if not found
*/
int binarySearch(int arr[], int left, int right, int target) {
// Base case: element not found
if (left > right) return -1;
int mid = left + (right - left) / 2;
// Found!
if (arr[mid] == target) return mid;
// Search left half
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
}
// Search right half
return binarySearch(arr, mid + 1, right, target);
}
/*
* Tower of Hanoi
* Move n disks from 'from' to 'to' using 'aux' as auxiliary
*/
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
cout << "Move disk 1 from " << from << " to " << to << endl;
return;
}
// Move n-1 disks from 'from' to 'aux'
hanoi(n - 1, from, aux, to);
// Move the largest disk
cout << "Move disk " << n << " from " << from << " to " << to << endl;
// Move n-1 disks from 'aux' to 'to'
hanoi(n - 1, aux, to, from);
}
// ============================================================
// EXERCISES:
// ============================================================
/*
* 1. Write a recursive function to find the length of a string
*
* 2. Write a recursive function to count digits in a number
*
* 3. Write a recursive function to check if array is sorted
*
* 4. Write a recursive function to print all permutations
* of a string
*
* 5. Implement merge sort using recursion
*/