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