Consider the recursive function defined below. Recall that for a non-empty list
ID: 3196949 • Letter: C
Question
Consider the recursive function defined below. Recall that for a non-empty list:
first(list) returns the first (left-most) element of list.
last(list) returns the last (right-most) element of list.
function fibtuple(n)
if n=1 then fibtuple [0,1]
else
listfibtuple(n1)
xfirst(list)
ylast(list)
fibtuple [y,x+y]
endif
endfunc
1. fibtuple(1) = [ ]. type the list brackets
2. fibtuple(2) = [ ]. type the list brackets
3. fibtuple(9) = [ ]. type the list brackets.
4. When computing fibtuple(9), how many additional times is the fibtuple() function called?
(Assume you are computing the function exactly as written and have not stored any previous results).
Explanation / Answer
1) fibtuple(1) = [0,1]
beacuse for n = 1, fibtuple(1) = [0,1]
2) for n=2
list <- fibtuple(1) => list <- [0,1]
x <- 0
y <- 1
So,
fibtuple(2) = [ 1. 1 ]
3) For n=9,
fibtuple(9) will call recursivly fibtuple(8), that in turn will call fibtuple(7), fibtuple(7) will call fibtuple(6) and so on.
In last, fibtuple(1) will be called, it will return [0,1]
fibtuple(2) will return [1,0+1] i.e [1,1]
fibtuple(3) will return [1, 1+1] i.e. [1, 2]
fibtuple(4) will return [2, 1+2] i.e. [2, 3]
fibtuple(5) will return [3, 2+3] i.e. [3, 5]
fibtuple(6) will return [5, 3+5] i.e. [5, 8]
fibtuple(7) will return [8, 5+8] i.e. [8, 13]
fibtuple(8) will return [13, 8+13] i.e. [13, 21]
fibtuple(9) will return [21, 13+21] i.e. [21, 34]
fibtuple(9) =. [21, 34]
4)
For computing fibtuple(9),
fibtuple() function called 8 times additionally.