cpp
exercises
exercises.cpp⚙️cpp
/**
* Recursion - Exercises
*
* Practice problems for understanding recursion in C++.
* Each exercise includes TODO sections to complete.
*
* Compile: g++ -std=c++17 -Wall -Wextra exercises.cpp -o exercises
* Run: ./exercises
*/
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
// ============================================================
// Exercise 1: Factorial ⭐
// ============================================================
/**
* Calculate n! = n × (n-1) × ... × 1
* Base case: 0! = 1! = 1
*
* Examples:
* factorial(0) = 1
* factorial(5) = 120
*/
long long factorial(int n) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 2: Sum of Numbers ⭐
// ============================================================
/**
* Calculate 1 + 2 + 3 + ... + n
* Base case: sumTo(0) = 0
*
* Examples:
* sumTo(5) = 15
* sumTo(10) = 55
*/
int sumTo(int n) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 3: Count Digits ⭐
// ============================================================
/**
* Count the number of digits in n
* Base case: single digit number returns 1
*
* Examples:
* countDigits(12345) = 5
* countDigits(7) = 1
*/
int countDigits(int n) {
// TODO: Implement recursively
// Hint: n / 10 removes last digit
return 0;
}
// ============================================================
// Exercise 4: Sum of Digits ⭐
// ============================================================
/**
* Calculate sum of all digits in n
* Base case: single digit returns itself
*
* Examples:
* sumDigits(123) = 6
* sumDigits(9999) = 36
*/
int sumDigits(int n) {
// TODO: Implement recursively
// Hint: n % 10 gives last digit
return 0;
}
// ============================================================
// Exercise 5: Power ⭐⭐
// ============================================================
/**
* Calculate base^exp
* Handle: exp = 0, positive exp, negative exp
*
* Examples:
* power(2, 5) = 32
* power(3, 0) = 1
* power(2, -2) = 0.25
*/
double power(double base, int exp) {
// TODO: Implement recursively
// Hint: x^(-n) = 1 / x^n
return 0.0;
}
// ============================================================
// Exercise 6: Reverse String ⭐⭐
// ============================================================
/**
* Reverse a string recursively
* Base case: empty or single char string
*
* Examples:
* reverseStr("hello") = "olleh"
* reverseStr("a") = "a"
*/
string reverseStr(const string& s) {
// TODO: Implement recursively
// Hint: reverse(rest) + first_char
return "";
}
// ============================================================
// Exercise 7: Is Palindrome ⭐⭐
// ============================================================
/**
* Check if string is a palindrome
* Base case: length 0 or 1 is palindrome
*
* Examples:
* isPalindrome("radar") = true
* isPalindrome("hello") = false
*/
bool isPalindrome(const string& s) {
// TODO: Implement recursively
// Hint: compare first and last, then check middle
return false;
}
// ============================================================
// Exercise 8: Fibonacci ⭐⭐
// ============================================================
/**
* Calculate nth Fibonacci number
* F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
*
* Examples:
* fib(0) = 0
* fib(1) = 1
* fib(10) = 55
*/
int fib(int n) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 9: GCD ⭐⭐
// ============================================================
/**
* Greatest Common Divisor using Euclidean algorithm
* gcd(a, b) = gcd(b, a % b), base: gcd(a, 0) = a
*
* Examples:
* gcd(48, 18) = 6
* gcd(17, 5) = 1
*/
int gcd(int a, int b) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 10: Binary Search ⭐⭐
// ============================================================
/**
* Find target in sorted array, return index or -1
*
* Examples:
* binarySearch({1,3,5,7,9}, 5) = 2
* binarySearch({1,3,5,7,9}, 4) = -1
*/
int binarySearch(const vector<int>& arr, int target, int low, int high) {
// TODO: Implement recursively
return -1;
}
int binarySearch(const vector<int>& arr, int target) {
return binarySearch(arr, target, 0, arr.size() - 1);
}
// ============================================================
// Exercise 11: Array Sum ⭐⭐
// ============================================================
/**
* Sum all elements in array recursively
*
* Examples:
* arraySum({1,2,3,4,5}) = 15
* arraySum({}) = 0
*/
int arraySum(const vector<int>& arr, int index = 0) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 12: Array Maximum ⭐⭐
// ============================================================
/**
* Find maximum element recursively
* Assume non-empty array
*
* Examples:
* arrayMax({3,1,4,1,5}) = 5
*/
int arrayMax(const vector<int>& arr, int index = 0) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 13: Count Occurrences ⭐⭐
// ============================================================
/**
* Count how many times target appears in array
*
* Examples:
* countOccur({1,2,3,2,2,4}, 2) = 3
* countOccur({1,2,3}, 5) = 0
*/
int countOccur(const vector<int>& arr, int target, int index = 0) {
// TODO: Implement recursively
return 0;
}
// ============================================================
// Exercise 14: Reverse Array ⭐⭐⭐
// ============================================================
/**
* Reverse array in place recursively
*
* Examples:
* {1,2,3,4,5} becomes {5,4,3,2,1}
*/
void reverseArray(vector<int>& arr, int left, int right) {
// TODO: Implement recursively
// Hint: swap left and right, then recurse on middle
}
void reverseArray(vector<int>& arr) {
if (!arr.empty()) {
reverseArray(arr, 0, arr.size() - 1);
}
}
// ============================================================
// Exercise 15: Print Pattern ⭐⭐⭐
// ============================================================
/**
* Print pattern recursively:
* printPattern(4) should print:
* ****
* ***
* **
* *
* *
* **
* ***
* ****
*/
void printPattern(int n) {
// TODO: Implement recursively
// Hint: print n stars, recurse, print n stars again
}
// ============================================================
// Exercise 16: Tower of Hanoi ⭐⭐⭐
// ============================================================
/**
* Solve Tower of Hanoi puzzle
* Print moves to transfer n disks from source to target using auxiliary
*
* Example for n=2:
* Move disk 1 from A to B
* Move disk 2 from A to C
* Move disk 1 from B to C
*/
void hanoi(int n, char source, char target, char auxiliary) {
// TODO: Implement recursively
}
// ============================================================
// Exercise 17: Generate Subsets ⭐⭐⭐
// ============================================================
/**
* Generate all subsets of {1, 2, ..., n}
*
* Example for n=2: {}, {1}, {2}, {1,2}
*/
void generateSubsets(int n, int current, vector<int>& subset,
vector<vector<int>>& result) {
// TODO: Implement recursively
}
vector<vector<int>> subsets(int n) {
vector<vector<int>> result;
vector<int> subset;
generateSubsets(n, 1, subset, result);
return result;
}
// ============================================================
// Exercise 18: Check Sorted ⭐⭐⭐
// ============================================================
/**
* Check if array is sorted in ascending order
*
* Examples:
* isSorted({1,2,3,4}) = true
* isSorted({1,3,2,4}) = false
*/
bool isSorted(const vector<int>& arr, int index = 0) {
// TODO: Implement recursively
return false;
}
// ============================================================
// TEST FUNCTIONS
// ============================================================
void testExercise1() {
cout << "\n=== Exercise 1: Factorial ===" << endl;
cout << "factorial(0) = " << factorial(0) << " (expected: 1)" << endl;
cout << "factorial(5) = " << factorial(5) << " (expected: 120)" << endl;
cout << "factorial(10) = " << factorial(10) << " (expected: 3628800)" << endl;
}
void testExercise2() {
cout << "\n=== Exercise 2: Sum To N ===" << endl;
cout << "sumTo(5) = " << sumTo(5) << " (expected: 15)" << endl;
cout << "sumTo(10) = " << sumTo(10) << " (expected: 55)" << endl;
}
void testExercise3() {
cout << "\n=== Exercise 3: Count Digits ===" << endl;
cout << "countDigits(12345) = " << countDigits(12345) << " (expected: 5)" << endl;
cout << "countDigits(7) = " << countDigits(7) << " (expected: 1)" << endl;
}
void testExercise4() {
cout << "\n=== Exercise 4: Sum Digits ===" << endl;
cout << "sumDigits(123) = " << sumDigits(123) << " (expected: 6)" << endl;
cout << "sumDigits(9999) = " << sumDigits(9999) << " (expected: 36)" << endl;
}
void testExercise5() {
cout << "\n=== Exercise 5: Power ===" << endl;
cout << "power(2, 5) = " << power(2, 5) << " (expected: 32)" << endl;
cout << "power(3, 0) = " << power(3, 0) << " (expected: 1)" << endl;
cout << "power(2, -2) = " << power(2, -2) << " (expected: 0.25)" << endl;
}
void testExercise6() {
cout << "\n=== Exercise 6: Reverse String ===" << endl;
cout << "reverseStr(\"hello\") = \"" << reverseStr("hello") << "\" (expected: \"olleh\")" << endl;
}
void testExercise7() {
cout << "\n=== Exercise 7: Palindrome ===" << endl;
cout << boolalpha;
cout << "isPalindrome(\"radar\") = " << isPalindrome("radar") << " (expected: true)" << endl;
cout << "isPalindrome(\"hello\") = " << isPalindrome("hello") << " (expected: false)" << endl;
}
void testExercise8() {
cout << "\n=== Exercise 8: Fibonacci ===" << endl;
cout << "fib(0) = " << fib(0) << " (expected: 0)" << endl;
cout << "fib(1) = " << fib(1) << " (expected: 1)" << endl;
cout << "fib(10) = " << fib(10) << " (expected: 55)" << endl;
}
void testExercise9() {
cout << "\n=== Exercise 9: GCD ===" << endl;
cout << "gcd(48, 18) = " << gcd(48, 18) << " (expected: 6)" << endl;
cout << "gcd(17, 5) = " << gcd(17, 5) << " (expected: 1)" << endl;
}
void testExercise10() {
cout << "\n=== Exercise 10: Binary Search ===" << endl;
vector<int> arr = {1, 3, 5, 7, 9, 11};
cout << "binarySearch({1,3,5,7,9,11}, 5) = " << binarySearch(arr, 5) << " (expected: 2)" << endl;
cout << "binarySearch({1,3,5,7,9,11}, 4) = " << binarySearch(arr, 4) << " (expected: -1)" << endl;
}
void testExercise11() {
cout << "\n=== Exercise 11: Array Sum ===" << endl;
cout << "arraySum({1,2,3,4,5}) = " << arraySum({1,2,3,4,5}) << " (expected: 15)" << endl;
cout << "arraySum({}) = " << arraySum({}) << " (expected: 0)" << endl;
}
void testExercise12() {
cout << "\n=== Exercise 12: Array Max ===" << endl;
cout << "arrayMax({3,1,4,1,5}) = " << arrayMax({3,1,4,1,5}) << " (expected: 5)" << endl;
}
void testExercise13() {
cout << "\n=== Exercise 13: Count Occurrences ===" << endl;
cout << "countOccur({1,2,3,2,2,4}, 2) = " << countOccur({1,2,3,2,2,4}, 2) << " (expected: 3)" << endl;
}
void testExercise14() {
cout << "\n=== Exercise 14: Reverse Array ===" << endl;
vector<int> arr = {1, 2, 3, 4, 5};
reverseArray(arr);
cout << "Reversed: ";
for (int n : arr) cout << n << " ";
cout << "(expected: 5 4 3 2 1)" << endl;
}
void testExercise15() {
cout << "\n=== Exercise 15: Print Pattern ===" << endl;
cout << "printPattern(3):" << endl;
printPattern(3);
}
void testExercise16() {
cout << "\n=== Exercise 16: Tower of Hanoi ===" << endl;
cout << "hanoi(3, 'A', 'C', 'B'):" << endl;
hanoi(3, 'A', 'C', 'B');
}
void testExercise17() {
cout << "\n=== Exercise 17: Subsets ===" << endl;
auto result = subsets(3);
cout << "subsets(3): ";
for (const auto& s : result) {
cout << "{";
for (size_t i = 0; i < s.size(); i++) {
cout << s[i] << (i < s.size()-1 ? "," : "");
}
cout << "} ";
}
cout << endl;
}
void testExercise18() {
cout << "\n=== Exercise 18: Is Sorted ===" << endl;
cout << boolalpha;
cout << "isSorted({1,2,3,4}) = " << isSorted({1,2,3,4}) << " (expected: true)" << endl;
cout << "isSorted({1,3,2,4}) = " << isSorted({1,3,2,4}) << " (expected: false)" << endl;
}
// ============================================================
// MAIN FUNCTION
// ============================================================
int main() {
cout << "╔════════════════════════════════════════════════════════════╗" << endl;
cout << "║ RECURSION - EXERCISES ║" << endl;
cout << "╚════════════════════════════════════════════════════════════╝" << endl;
testExercise1();
testExercise2();
testExercise3();
testExercise4();
testExercise5();
testExercise6();
testExercise7();
testExercise8();
testExercise9();
testExercise10();
testExercise11();
testExercise12();
testExercise13();
testExercise14();
testExercise15();
testExercise16();
testExercise17();
testExercise18();
cout << "\n╔════════════════════════════════════════════════════════════╗" << endl;
cout << "║ Complete the TODO sections and re-run! ║" << endl;
cout << "╚════════════════════════════════════════════════════════════╝" << endl;
return 0;
}
// ============================================================
// ANSWER KEY
// ============================================================
/*
long long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int sumTo(int n) {
if (n <= 0) return 0;
return n + sumTo(n - 1);
}
int countDigits(int n) {
n = abs(n);
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
int sumDigits(int n) {
n = abs(n);
if (n < 10) return n;
return (n % 10) + sumDigits(n / 10);
}
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);
}
string reverseStr(const string& s) {
if (s.length() <= 1) return s;
return reverseStr(s.substr(1)) + s[0];
}
bool isPalindrome(const string& s) {
if (s.length() <= 1) return true;
if (s.front() != s.back()) return false;
return isPalindrome(s.substr(1, s.length() - 2));
}
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int gcd(int a, int b) {
if (b == 0) return abs(a);
return gcd(b, a % b);
}
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 arraySum(const vector<int>& arr, int index) {
if (index >= (int)arr.size()) return 0;
return arr[index] + arraySum(arr, index + 1);
}
int arrayMax(const vector<int>& arr, int index) {
if (index == (int)arr.size() - 1) return arr[index];
return max(arr[index], arrayMax(arr, index + 1));
}
int countOccur(const vector<int>& arr, int target, int index) {
if (index >= (int)arr.size()) return 0;
int count = (arr[index] == target) ? 1 : 0;
return count + countOccur(arr, target, index + 1);
}
void reverseArray(vector<int>& arr, int left, int right) {
if (left >= right) return;
swap(arr[left], arr[right]);
reverseArray(arr, left + 1, right - 1);
}
void printPattern(int n) {
if (n <= 0) return;
for (int i = 0; i < n; i++) cout << "*";
cout << endl;
printPattern(n - 1);
for (int i = 0; i < n; i++) cout << "*";
cout << endl;
}
void hanoi(int n, char source, char target, char auxiliary) {
if (n == 0) return;
hanoi(n - 1, source, auxiliary, target);
cout << "Move disk " << n << " from " << source << " to " << target << endl;
hanoi(n - 1, auxiliary, target, source);
}
void generateSubsets(int n, int current, vector<int>& subset,
vector<vector<int>>& result) {
if (current > n) {
result.push_back(subset);
return;
}
subset.push_back(current);
generateSubsets(n, current + 1, subset, result);
subset.pop_back();
generateSubsets(n, current + 1, subset, result);
}
bool isSorted(const vector<int>& arr, int index) {
if (index >= (int)arr.size() - 1) return true;
if (arr[index] > arr[index + 1]) return false;
return isSorted(arr, index + 1);
}
*/