Given: procedure a(n: int) { if n == 0 then a(n) =: 1 else a(n) =: a(n-1) * a(n-

Question

Given:

procedure a(n: int) {
if n == 0 then
a(n) =: 1
else
a(n) =: a(n-1) * a(n-2)
}

a) Write out a trace of calls for the following algorithm starting with a(4)
b) What do you think this algorithm does? Please summarize input, output, and the formula it is calculating. Note that the algorithm may have bugs
c) Does the algorithm need fixing? If so please enter a fixed version here

Explanation / Answer

(a) a(4)---> n=4, a(4)=a(3)*a(2) call a(3)--> n=3, a(3)=a(2)*a(1) call a(2)--> n=2, a(2)=a(1)*a(0) call a(1)--> n=1, a(1)=a(0)*a(-1) here is the bug because a(-1) has no value, and only a(0) can return value 1....This will produce error in the calculating procedure. (a(4) can only be evaluated after the bug is fixed, so I would should this step on part(c)) (b)This algorithm is used to calculate a(n) which is defined as a(n)=a(n-1)*a(n-2)....each term is the product of the previous two terms....Note that this is not Fibonacci number which is defined by b(n)=b(n-1)+b(n-2).....It is product of previous two terms...... Of course in order to solve a(n), we need two initial conditions....This program only provide one initial condition...That's why it has bugs and don't even return out the final value..... (c) In order to fix it, we need to add another initial condition.....I just choose a(1)=2; Since the problem is not specified, we can just pick one value.... Code should be fixed: procedure a(n: int) { if n == 0 then a(n) =: 1 else if n==1 then a(n)=: 2 else a(n) =: a(n-1) * a(n-2) } NOW let's repeat part(a) to see what is the value of a(4) a(4)---> n=4, a(4)=a(3)*a(2) call a(3)--> n=3, a(3)=a(2)*a(1) call a(2)--> n=2, a(2)=a(1)*a(0) call a(1)--> n=1, a(1)=2 call a(0)--> n=0, a(0)=1 substitute it back: a(2)=a(1)*a(0)=2*1=2 a(3)=a(2)*a(1)=2*2=4 a(4)=a(3)*a(2)=4*2=8 Of course, different value of a(1) would give u different value of a(4)......

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.