CODEWITHSUNDEEP
haskell
Pete
Pete

Reputation: 170

Evaluating recursive function in Haskell

I am given this function and asked to manually evaluate g 5. I found the answer to be 25, but this is incorrect. The correct answer is 63. Would anyone help me understand why? Thanks

g :: Int -> Int
g n 
  | n==0      = 1
  | otherwise = 2 * g (n-1) + 1

My answer: (2*4+1) + (2*3+1) + (2*2+1) + (2*1+1) + 1 = 25

Upvotes: 1

Views: 428

Answers (4)

Carcigenicate
Carcigenicate

Reputation: 45736

You just need to think it out step by step:

(g 5) = 2 * (g 4) + 1
(g 4) = 2 * (g 3) + 1
(g 3) = 2 * (g 2) + 1
(g 2) = 2 * (g 1) + 1
(g 1) = 2 * (g 0) + 1
(g 0) = 1

Then, plug in the values from the bottom-up:

2 * 1 + 1 = 3
2 * 3 + 1 = 7
2 * 7 + 1 = 15
2 * 15 + 1 = 31
2 * 31 + 1 = 63

Your problem is that you were using the raw value of n, instead of what (g n) returned at the end of the recursion.

Upvotes: 8

Jonathan Cast
Jonathan Cast

Reputation: 4635

Your parenthesization is wrong. Not doing any reductions (other than expanding g), we get

g 5
= 2 * g 4 + 1
= 2 * (2 * g 3 + 1) + 1
= 2 * (2 * (2 * g 2 + 1) + 1) + 1
= 2 * (2 * (2 * (2 * g 1 + 1) + 1) + 1) + 1
= 2 * (2 * (2 * (2 * (2 * g 0 + 1) + 1) + 1) + 1) + 1
= 2 * (2 * (2 * (2 * (2 * 1 + 1) + 1) + 1) + 1) + 1

Upvotes: 0

RussAbbott
RussAbbott

Reputation: 2738

Although this isn't your question, it's fairly easy to show by induction that

g n = 2^(n+1)-1

So 

g 5 = 2^6 - 1 --> 63

Upvotes: 0

Julia Path
Julia Path

Reputation: 2366

In your calculation you messed up with the nesting of the terms. They should be nested and not summed up separately.

The way to evaluate such functions is to replace function applications with the body of the function with its parameters replaced by the given arguments. I will do the first few steps and then you can take over:

g 5
if 5 == 0 then 1 else 2 * g (5-1) + 1
2 * g (5-1) + 1
2 * (if (5 - 1) == 0 then 1 else 2 * g ((5-1) - 1) + 1) + 1
2 * (if 4 == 0 then 1 else 2 * g (4-1) + 1) + 1
2 * (2 * g (4-1) + 1) + 1
...
63

@Carcigenicate's answer is of course easier to calculate, but this technique is more universal and more inline with how the code actually works.

Upvotes: 2

Related Questions