I am new to Haskell Programming. I tried to write a Haskell function to get the factorial of any given number by recursion. But it gets stack overflow exception.

  factor x = x * (factor x-1)

CodePudding user response：

You are getting the error since your recursion doesn't have a base case. You need a way for the program to stop once a certain condition is met.

CodePudding user response：

There are many ways of doing the factorial calculation - recursion, product, or folds.

factorial n = product [1..n]    -- product algorithm

import Data.List
factorial n = foldl' (*) 1 [1..n]     -- fold algorithm

In the case of recursion, we always have two things:

1. The base case
2. How to get from one case to another

Considering some factorials:

1! = 1
2! = 2 x 1 = 2 x 1!
3! = 3 x 2 x 1 = 3 x 2!
4! = 4 x 3 x 2 x 1 = 4 x 3!

The base case, the final case, is 1!, or 1. The way of getting from n! to (n-1)! is to multiply n by (n-1)!

When we set out the factorial calculation, we have to do the base case first, otherwise Haskell will pattern match on the general case and never get to the base case. Also, it is a good practice to explicitly specify the types, in this case Integer (arbitrary sized integer) to Integer (arbitrary sized integer).

 factor :: Integer -> Integer
 factor 1 = 1
 factor n = n * factor (n-1)