C++ Recursion

🔁 C++ Recursion

Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller subproblems.
Every recursive function must have:

  1. Base case – stops recursion

  2. Recursive case – calls itself with a smaller input

🔹 1. Basic Syntax

return_type functionName(parameters) {
if (base_condition)
return value; // base case

return functionName(smaller_problem); // recursive call
}

🔹 2. Simple Example (Print Numbers)

void print(int n) {
if (n == 0)
return;

cout << n << " ";
print(n - 1);
}

int main() {
print(5);
}

Output:

5 4 3 2 1

🔹 3. Factorial Using Recursion

int factorial(int n) {
if (n == 1)
return 1;

return n * factorial(n - 1);
}

int main() {
cout << factorial(5);
}

Output:

120

🔹 4. Fibonacci Series (Recursive)

int fib(int n) {
if (n <= 1)
return n;

return fib(n - 1) + fib(n - 2);
}

int main() {
cout << fib(6);
}

Output:

8

🔹 5. Sum of Digits Using Recursion

int sumDigits(int n) {
if (n == 0)
return 0;

return (n % 10) + sumDigits(n / 10);
}

int main() {
cout << sumDigits(1234);
}

Output:

10

🔹 6. Reverse a Number (Recursive)

void reverse(int n) {
if (n == 0)
return;

cout << n % 10;
reverse(n / 10);
}

🔹 7. Recursion vs Loop

Recursion Loop
Function calls itself Repeats using iteration
Uses stack memory Uses less memory
Cleaner for problems like trees Faster for simple repetition
Risk of stack overflow No stack overflow

🔹 8. Common Mistakes ❌

❌ Missing Base Case

void fun() {
fun(); // infinite recursion
}

➡ Causes stack overflow

❌ Wrong Base Condition

if (n < 0) return 1; // incorrect logic

🔹 9. Tail Recursion

Recursive call is the last statement.

void print(int n) {
if (n == 0)
return;

cout << n << " ";
print(n - 1);
}

✔ Easier to optimize
✔ Similar to loops

🔹 10. When to Use Recursion

  • Tree and graph traversal

  • Divide and conquer algorithms

  • Problems with repetitive structure

  • Mathematical definitions (factorial, Fibonacci)

📌 Summary

  • Recursion = function calling itself

  • Must have a base case

  • Solves problems by reducing size

  • Elegant but uses more memory

  • Avoid deep recursion if possible

You may also like...