Recursion and PMI

PMI (principal of mathematical induction).
we will solve recursion problem to think in sense of PMI only

we don't have to think entirely just think some of step

steps:

1. prove f(0) or f(1) is true (base case)
2. Induction Hypothesis: assume that f(k) is true
3. Induction step: using 2 prove that f(k + 1) is true

for example

#include <iostream>
using namespace std;

int factorial(int n) {
    cout << n << endl;
    if (n == 0) { // we taking base case in which it's run perfectly
        return 1;
    }
    int smallOutput = factorial(n - 1); // according to PMI we assume the small run than it will also run
    return n * smallOutput;
}

int main() {
    int n;
    cin >> n;
    int output = factorial(n);
    cout << output << endl;
}

example 2: with two base case

int fib(int n){
    if(n == 0){
        return 0;
    }
    if(n == 1){
        return 1;
    }
    int smallOutput1 = fib(n - 1);
    int smallOutput2 = fib(n - 2);
    return smallOutput1 + smallOutput2;
} 

for more details: click here