CODEWITHSUNDEEP
haskellrecursiontail-recursion
immi0815
immi0815

Reputation: 39

What's the difference between tail and guarded recursion?

In my exercise I have to decide what kind of recursion the functions are.

We have to choose from linear recursion, tail recursion and guarded recursion but I don't really understand the difference between the last two.

Can some one explain the difference between guarded and tail recursion?

The functions we have to differentiate for reference:

pow2 0 = 1
pow2 n = 2 * pow2 (n-1)

factAux r i n
  | i <= n = factAux (i * r) (i + 1) n | otherwise = r
factorial = factAux 1 1

init [x] = []
init (x:xs) =  x : init xs

binom n 0 = 1
binom n k
  | n == k = 1
  | otherwise = binom (n - 1) k + binom (n - 1) (k - 1)

negList [] = []
negList (x : xs) = if x > 0 then negList (-x : xs) else x : negList xs

Upvotes: 2

Views: 419

Answers (1)

radrow
radrow

Reputation: 7129

I won't solve your homework as it would be counter-educative.

Instead, I will answer the question in the post's title:

Tail recursion

A call is tail-recursive when

  • It's recursive
  • The result of that call is returned immediately, without any modification or action done after it

For example:

-- This is tail-rec
f x = if x == 0
      then 0
      else f (x + 1)

-- This is not
g x = if x == 0
      then 0
      else g (x + 1) - 1

-- And this is not too
h x = h (h x)

For more info, check this thread.

Guarded recursion

This occurs when a recursive call is positioned under a lazy parameter to a data constructor:

-- This is guarded-rec
f x = if x == 0
      then []
      else x : f (x - 1)  -- (:) is lazy on both operands

-- And this is not
g x = if x == 0
      then []
      else g (x - 1)

-- And this is not too
data StrictList a = SNil | SCons !a !(StrictList a)
h x = if x == 0
      then SNil
      SCons x (h x)

Cross-examples

This link may help you seeing the difference. Also check out this, although it gives examples in Prolog.

Tail rec and guard rec

This is contradictory, as guarding a recursive call with a constructor breaks the "doing nothing to the result" requirement of tail recursion.

Tail rec and not guard rec

f x = f x

Not tail rec and guard rec

f x = x : f x

Not tail rec and not guard rec

f x = f x + 1

Upvotes: 5

Related Questions