DEV Community

Ayush Ranjan
Ayush Ranjan

Posted on

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
} 
Enter fullscreen mode Exit fullscreen mode

for more details: click here

Discussion (0)