C++ Recursion
Understanding functions that call themselves
🔄 What is Recursion?
Recursion is a programming technique where a function calls itself to solve smaller subproblems. It's like breaking a big problem into smaller, similar pieces until you reach a simple base case.
// Simple recursive function to calculate factorial
int factorial(int n) {
if (n <= 1) return 1; // Base case
return n * factorial(n - 1); // Recursive call
}
Output for factorial(5):
5! = 5 × 4 × 3 × 2 × 1 = 120
Key Recursion Concepts
Base Case
The stopping condition that prevents infinite recursion
if (n <= 1) return 1;Recursive Call
Function calling itself with modified parameters
return n * factorial(n - 1);Call Stack
Memory structure storing function calls
factorial(3) → factorial(2) → factorial(1)Tail Recursion
Optimized recursion where recursive call is last
return helper(n-1, acc*n);🔹 Basic Recursion Example
Recursion involves a function calling itself to solve problems by breaking them into smaller
subproblems. A classic example is a countdown:
void countdown(int n) { if (n>0) { cout << n; countdown(n-1); } }. Recursion simplifies algorithms for
tasks like tree traversal, factorial computation, or divide-and-conquer strategies. However, it requires base cases
to avoid infinite loops and mindful stack usage. Recursion is a fundamental technique in C++ for elegant solutions
to repetitive or hierarchical problems.
#include <iostream>
using namespace std;
void countdown(int n) {
if (n <= 0) { // Base case
cout << "Blast off!" << endl;
return;
}
cout << n << " "; // Print current number
countdown(n - 1); // Recursive call
}
int main() {
countdown(5);
return 0;
}Output:
5 4 3 2 1 Blast off!
🔹 Fibonacci Sequence
The Fibonacci sequence is a classic example of recursion in programming. Each number in the series is the sum of the two preceding ones, starting from 0 and 1. For instance, the sequence begins 0, 1, 1, 2, 3, 5, 8, 13, and continues infinitely. This pattern appears in nature, mathematics, and computer algorithms, often used to teach recursive problem-solving and dynamic programming techniques to optimize repeated calculations.
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n; // Base cases: fib(0)=0, fib(1)=1
return fibonacci(n-1) + fibonacci(n-2); // Recursive relation
}
int main() {
for (int i = 0; i < 8; i++) {
cout << fibonacci(i) << " ";
}
return 0;
}Output:
0 1 1 2 3 5 8 13
🔹 Tree Traversal
Recursion is exceptionally well-suited for navigating tree-like data structures. Methods like in-order, pre-order, and post-order traversal use recursive calls to visit each node systematically. For example, an in-order traversal of a binary search tree visits the left subtree, then the root node, then the right subtree, producing a sorted output. This approach simplifies complex hierarchical data processing.
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return; // Base case
inorderTraversal(root->left); // Visit left subtree
cout << root->data << " "; // Process current node
inorderTraversal(root->right); // Visit right subtree
}For a binary tree with nodes 1,2,3:
Output: 2 1 3 (left-root-right order)