## DEV Community is a community of 846,721 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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;
}
``````