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
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.
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 = ....
head,tailshould be avoided when possible, and here there is no reason to use them.