CODEWITHSUNDEEP
haskellrecursion
hiboss
hiboss

Reputation: 317

Tail recursion vs Primitive Recursion

I am studying about haskell recursion. and when i read about recursion topic which talk about this two different type of recursion. i am understand how tail recursion works and its step to be done. i am not understand how is primitive recursion done in background. can anyone here help explain more about primitive and given some example ? For example : tail recursion

 sum:: [Int] -> Int
 sum [] = 0  
 sum (x:xs) = x+ (sum xs)

process of sum [1,2,3,4]:

  = 1 + sum[2,3,4]
  = 1 + (2 + sum [3,4] )
  = 1 + ( 2 + ( 3 + sum[4]) )
  = 1 + (2 +  (3 ( 4 + sum[])))
  = 1 + (2 + ( 3 + ( 4 + 0 ) ) )  
  = 10

How does primitive recursion works?

Upvotes: 1

Views: 834

Answers (1)

chi
chi

Reputation: 116139

Intuitively, we have tail recursion when we have a recursive function such that, when a recursive call is performed, the result of that call is the result of the function. In a sense, after the recursive call "there is nothing more to be done".

-- tail recursion
f1 n = if ... then ... else f1 (n - 1)
-- not tail recursion
f2 n = if ... then ... else 5 * f2 (n - 1)

Primitive recursion is another beast. We have primitive recursion when every recursive call is done using an argument which is a "direct subterm" of the original one.

-- primitive recursion (& non-tail recursion)
f1 (x:xs) = g x (f1 xs)   -- xs is  asubterm of x:xs

-- a tree type
data T = K Int T T
-- primitive recursion (& non-tail recursion)
f2 (K n l r) = h n (f2 l) (f2 r)                    -- l, r are subterms
-- non-primitive recursion (& tail recursion)
f3 (K n l (K m rl rr)) = f3 (K m (K n rl l) rl)     -- not a subterm

Upvotes: 5

Related Questions