Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

Hi everyone,

I'm really stuck on the following two questions. In essence, our lecturer went through these examples in class and a week later, the exact same questions were put to our lab demonstrator from a student who failed to grasp the original lecture. The problem? the demonstrator's answers were completely different to those of the lecturer. The demonstrator is adamant she is right, and the lecturer has not returned our emails yet because we have broken up for the Christmas holidays.

Question 1

Given the function f, where

f(0) = 3
f(n+1) = ceil(f(n)/2) + 1 (ceil = ceiling function)
Evaluate f(19)

Question 2

f(0) =1
f(n+1) = 2*f(n) +1
Evaluate the f(3)

Just to demonstrate this is not a homework assignment etc - please just provide the answer to both - without the method if you wish.
For those who are curious the results we have so far is;

Question 1 Lecturer Ans = 21 Demonstrator = 3
Question 2 Lecturer Ans = 15 Demonstrator = 18

This is very frustrating as we have an exam with recursive algorithms. Can someone please help?? How on earth can they be polar opposites??

I get:

1.) 3 (closed form )

2.) 15 (closed form )

It would help you more if you post your attempt at a solution.

It's 2:0 in favour of your lecturer.

Thank you both for your replies, this is wrecking my head!!
here is my attempt from question 2 - which follows what the lecturer did
for question 2;

f(0+1) = 2*f(0) +1
f(1) = 2*1+1
f(1) = 2+1
f(1) = 3

f(1+1) = 2*f(1)+1
f(2) = 2*f(1)+1
f(2) = 2*3+1
f(2) = 6+1
f(2) = 7

f(2+1) = 2*f(2)+1
f(3) = 2*7+1
f(3) = 14+1
f(3) = 15

Ans = 15

I'm going to have to root out question one, you both believe the answer is 3? Is it that every value put into the function will return 3 each time?
Or is it that 1 simply gets added each time the function runs, so to run up to f(19) thats 18 times +1 , plus the 3 = 21?

I get 3 for any appropriate n for the first one, since .

For the second one, I used symbolic differencing to get the homogeneous linear recursion:



whose characteristic roots are , hence the closed form is:



and using initial values to determine the parameters, we find:

Q1) I got 21 for this. Considering the fact that the questions are on recursive functions I would assume that one should work from the f(19) back to the base case. With this in mind it works out that there are 18 +1s and a 3 for the base case which gives 21. If we work from the f(0) up to the f(19) we can see that the function just returns 3 every time so I am still somewhat unclear on the method one should use in the case of recursive functions

Q2) I got 5 for this. Here's the method I used. I'm not really too confident on it's validity but I'm only posting it to offer another perspective on the questions. I used the same method for q1 too.

f(3) = 2*f(2) + 1
= 2*f(1) + 1 + 1
= 2*f(0) + 1 + 1 + 1
= 2*1 + 1 + 1 + 1
= 5

I'm afraid that's wrong chuck.

See MarkFL2's post above.

Don't know why I posted what I did above.

Simplest approach in this case where we only want f(3) is to work out f(1), f(2), f(3) in that order.

3, 3, 3......

1, 3, 7, 15........