Factorial - LISP(Scheme)

A Program for finding factorial using Scheme

Factorials n or n! is defined as product of all positive integers upto n.  Simply n! 

for example : 

5! = 5 * 4 * 3 * 2 * 1

Now there are two ways to calculate factorials, one is if we go in a backward direction i.e  in a decremental manner in which we recursively multiply the factorial(n-1) with n or we can go in an incremental manner in which we start from one and progress towards n i.e. 1 * 2 * 3 * ... * n-1 * n.

Aside from that , another condition which we need to know is 0! = 1.

In this post we will look how to implement the same in scheme.

When going in backward direction our scheme code will look like :

(define (fact n)(cond ((= n 1) 1)

                                   ((= n 0) 1)

                                   (else (* n (fact (- n 1))))))

In the above code we simply handle the possible edge cases first and continue until we reach the edge case. i.e. n == 1 or n == 0

Similarly we can define for an incremental iterative approach as : 

(define (fact n t)(cond((> n 0) (fact (- n 1) (* t n)))
                                     ( else t)))

Benefit of the incremental iterative approach is that if we know the state values, we can start directly from that particular state for example :
2nd state of 5! is :  t = 5 , n = 4
3rd state of 5! is :   t = 20 , n = 3
and so on...

Written By,

Sarvesh Bhatnagar