Topic 1

Recursion

What is Recursion?

A function that calls itself to solve smaller sub-problems. Every recursive function needs:

Base Case — stops the recursion
Recursive Case — function calls itself with simpler input

Each call is pushed onto the call stack. When base case is hit, calls return one by one (unwinding).

⚡

LIFO in call stack — Last called function returns first. Print AFTER recursive call = ascending.

🎯

Base case is mandatory — Without it → infinite recursion → stack overflow.

🔬

Print before call = descending. Print after call = ascending.

📊

Time: O(n) for linear recursion. Space: O(n) due to call stack.

#include <iostream>
using namespace std;

void f(int x) {
    if (x > 0) {
        cout << x;
        f(x - 2);
        cout << x;
    }
}

int main() {
    f(5);    // Output: 5 3 1 1 3 5
    return 0;
}

#include <iostream>
using namespace std;

void f(int x) {
    if (x > 0) {
        f(x - 1);
        cout << x;
    }
}

int main() {
    f(5);    // Output: 1 2 3 4 5
    return 0;
}

#include <iostream>
using namespace std;

int cal(int b, int p) {
    if (p != 0) {
        return (b * cal(b, p - 1));
    } else {
        return 1;
    }
}

int main() {
    cout << cal(2, 3);    // Output: 8
    return 0;
}

#include <iostream>
using namespace std;

int fac(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return (n * fac(n - 1));
}

int main() {
    cout << fac(5);    // Output: 120
    return 0;
}

#include <iostream>
using namespace std;

string reverseString(string s) {
    // Base case
    if (s.length() == 0)
        return s;

    // Recursive case: move first char to end
    return reverseString(s.substr(1)) + s[0];
}

int main() {
    string text = "Hello";
    cout << reverseString(text);    // Output: olleH
    return 0;
}

#include <iostream>
using namespace std;

int product(int a, int b) {
    // Base case
    if (b == 0)
        return 0;

    // Recursive: a * b = a + a*(b-1)
    return a + product(a, b - 1);
}

int main() {
    int num1, num2;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    cout << "Product = " << product(num1, num2);
    return 0;
}

#include <iostream>
using namespace std;

int countDigits(int n) {
    // Base case
    if (n == 0)
        return 0;

    // Recursive case
    return 1 + countDigits(n / 10);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;

    if (num == 0)
        cout << "Number of digits = 1";
    else
        cout << "Number of digits = " << countDigits(num);
    return 0;
}

#include <iostream>
using namespace std;

int sumDigits(int n) {
    // Base case
    if (n == 0)
        return 0;

    // Recursive case: last digit + sum of rest
    return (n % 10) + sumDigits(n / 10);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    cout << "Sum of digits = " << sumDigits(num);
    return 0;
}

Exam Tip — Tracing Output

For f(5) where print is before AND after call: 5 3 1 1 3 5

Going IN: prints 5, 3, 1 — Coming BACK: prints 1, 3, 5

Pattern: n % 10 = last digit, n / 10 = remove last digit