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:
- prove f(0) or f(1) is true (base case)
- Induction Hypothesis: assume that f(k) is true
- 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
Top comments (0)