Recursion
Functions calling themselves
Interview Relevant: Very common in interviews
Recursion
Recursion is when a function calls itself to solve smaller subproblems.
Key Components
- Base case: Condition to stop recursion
- Recursive case: Function calls itself with smaller input
- Stack frames: Each call uses stack memory
Code Examples
Common recursive algorithms and optimizations.
cpp
1// Factorial
2int factorial(int n) {
3 if (n <= 1) return 1; // Base case
4 return n * factorial(n - 1); // Recursive case
5}
6
7// Fibonacci
8int fibonacci(int n) {
9 if (n <= 1) return n;
10 return fibonacci(n - 1) + fibonacci(n - 2);
11}
12
13// Fibonacci with memoization
14int fib(int n, vector<int>& memo) {
15 if (n <= 1) return n;
16 if (memo[n] != -1) return memo[n];
17 return memo[n] = fib(n-1, memo) + fib(n-2, memo);
18}
19
20// Binary search (recursive)
21int binarySearch(vector<int>& arr, int target, int left, int right) {
22 if (left > right) return -1;
23 int mid = left + (right - left) / 2;
24 if (arr[mid] == target) return mid;
25 if (arr[mid] > target)
26 return binarySearch(arr, target, left, mid - 1);
27 return binarySearch(arr, target, mid + 1, right);
28}
29
30// Tail recursion (can be optimized by compiler)
31int factorialTail(int n, int acc = 1) {
32 if (n <= 1) return acc;
33 return factorialTail(n - 1, n * acc);
34}