CODEWITHSUNDEEP
haskellrecursion
Gloria95
Gloria95

Reputation: 139

Tail recursion in Haskell for a function

I am trying to learn Haskell and I read about tail recursions. For example I can write the sum function this way :

sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + summe xs

But also this way 

summe':: Num a => [a] -> a
summe' x = iterate x 0
    where
    iterate x y | null x    = 0 + y
                | otherwise = iterate (tail x) (head x + y)

Could someone tell me how to do it with this function? I am lost

f :: Integer -> Integer
f 0 = 0
f n = n * f (n-1) + n

Upvotes: 3

Views: 593

Answers (2)

Igor Drozdov
Igor Drozdov

Reputation: 15045

In order to rewrite the following function using tail-recursion:

f :: Integer -> Integer
f 0 = 0
f n = n * f (n-1) + n

the same approach, which used in summe' can be used.

The idea is to start from zero and increment the value until n is reached:

f :: Integer -> Integer
f n = iterate 0 0
  where
    f' x sum = x * sum + x
    iterate x sum | x == n = f' n sum
                  | otherwise = iterate (x + 1) (f' x sum)

Thus, if n is reached, evaluate the function with n and the accumulated sum; otherwise, calculate the function with intermediate sum and value and pass it to the next iteration.

Upvotes: 2

Will Ness
Will Ness

Reputation: 71070

Well, flipping the "time direction" in f n = n * f (n-1) + n by letting n = k + 1, we have

f (k+1) = (k+1) * f k + (k+1)
next fk k = (k+1) * fk + (k+1)

and thus

f n = iterate 0 0
  where
  iterate k fk | k==n = fk
               | otherwise = ....

Upvotes: 1

Related Questions