2

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
amalloy
  • 89,153
  • 8
  • 140
  • 205
immi0815
  • 39
  • 3
  • 2
    You should read [Open letter to students with homework problems](https://softwareengineering.meta.stackexchange.com/q/6166), Sure we could help you, but that would rob you of the education of doing it yourself. – cafce25 Jan 10 '23 at 07:55
  • 1
    to be clear: I dont want you to solve the problems, but I hope somebody could explain me the difference between guarded recursion and tail recursion:) – immi0815 Jan 10 '23 at 07:58
  • 3
    See [the Haskell Wiki on tail recursion](https://wiki.haskell.org/Tail_recursion). – molbdnilo Jan 10 '23 at 08:06
  • 1
    In that case I'd remove the code (or at least the linearly recursive functions) since they are not relevant to the question. – cafce25 Jan 10 '23 at 08:19
  • 4
    @cafce25 Helping doesn't always rob of education. What we don't want to do is solve things for you. Your link says lots of stuff I agree with, I just don't think your one-sentence summary really does it justice. – amalloy Jan 10 '23 at 08:19
  • 1
    @amalloy you're right, part of it is I misunderstood the question slightly, and yes I'm bad at words. – cafce25 Jan 10 '23 at 08:22

1 Answers1

5

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
radrow
  • 6,419
  • 4
  • 26
  • 53