and state why? Q2. Which item is correct about the following recursive algorithm

Question

and state why?

Q2.

Which item is correct about the following recursive algorithm? Fibonacci(x) {if (x = = 0) return 0;//stopping conditions if (x = = 1) return 1; return Fibonacci (x - 1) + Fibonacci(x - 2);} Linear but not tail recursion Linear and binary recursion Linear and tail recursion Not linear and Not binary recursion Not linear but binary recursion Suppose that A = {1, 2, 3, 4, 5}, What does the following algorithm return, if we call DOIT (A, 4)? Algorithm DOIT (A, n): Input: An integer array A and an integer n, such that A has at least n elements if n = 1 then return A [0] else return DOIT (A, n - 1) + A [n - 1] 15 10 9 A = {1, 3, 4, 8, 16} A = {1, 1, 1, 1, 1}

Explanation / Answer

Q1)

A binary-recursive routine (potentially) calls itself twice.

Ans: Not linear but binary recursion

Q2.

Ans. b

A = {1, 2, 3, 4,5};

DOIT(A, 4)

   A[3] + DOIT(3)
   => A[3] + A[2] + DOIT(2)
   => A[3] + A[2] + A[1] + DOIT(1)
   => A[3] + A[2] + A[1] + A[0]

   = 4 + 3 + 2 + 1
   =10

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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