The Three Laws of Recursion

A recursive algorithms must satisfy below three things.

    (1) A recursive algorithm must have a base case.
    (2) A recursive algorithm must change its state and move toward the base case.
    (3) A recursive algorithm must call itself.

    Let us understand these steps by designing a recursive solution of calculating
    factorial of a given positive number. Let N=5.
    
    5! = 5 * 3 * 2 * 1 = 120.
     
    Here we can write 5! = 5 * 4! or 5! = 5 *(5 -1)!
    if we replace 5 with n then we can write n! = n × (n−1)! , where n is 5 ( as a example ).
     
   Let us see the recursive solution of factorial calculation. The implementation is satisfying the three
   condition of recursion.

#include<stdio.h>
#include <assert.h>

unsigned long fact (unsigned long n);

int main ()
{
 
  printf ("%ld \n", fact (5));
  return 0;
}

unsigned long
fact (unsigned long n)
{
  if (n == 0) // base condition
    return 1;
  else
    return (n * fact (n - 1)); // this will grow towards base
                               // conditio and call itself
}



Related Contents to follow