DEV Community

Ayush Ranjan
Ayush Ranjan

Posted on

Recursion and PMI

#cpp #beginners #computerscience

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

Top comments (0)