1. Consider the following algorithm: Algorithm rec Fun(x, y, n) ifn rec Function(val - 1)...

Transcribed Image Text:

1. Consider the following algorithm: Algorithm rec Fun(x, y, n) ifn<1 else if n-1 return Null return x + y else return (x + y) * rec Fun(x, y, n-1) a. What is the base condition? b. How do the recursive calls reach the base condition? c. Show a complete trace of the following algorithm and count the number of steps you perform. a. Using the input x=4 and n-3 b. Using the input x = 2 and n = 7 d. What does this algorithm do? e. Write an iterative algorithm that does the same function. 2. Consider the following algorithm: Algorithm rec Function(val) if (val <1) print"... else return print val+">>" rec Function(val - 1) // print is used to signify screen output. Anything between // the quotation marks t is displayed as is and the + // concatenates the two parts on the screen Ile.g. if you have x=253 then print x+" // 253---253 +x will print print "<<"+ val return a. What is the base condition? b. How do the recursive calls reach the base condition? c. Show a complete trace of the following algorithm and count the number of steps you perform. a. Using the input val - 2 b. Using the input val = 8 3. Write a recursive algorithm to calculate the Fibonacci number (https://en.wikipedia.org wiki Fibonacci number). The Fibonacci number of an input value x is calculated as fib(x) = fib(x-1)+ fib(x-2); Also it is known that fib(0) = 0 and fib(1) = 1 For example if x = 4 then fib(4) = fib(3) +fib(2) fib(2) + fib(1) + fib(1) + fib(0) fib(1) +0 +fib(0) +fib(1) +fib(1) +fib(0) +1 +1 +0 =3 1. Consider the following algorithm: Algorithm rec Fun(x, y, n) ifn<1 else if n-1 return Null return x + y else return (x + y) * rec Fun(x, y, n-1) a. What is the base condition? b. How do the recursive calls reach the base condition? c. Show a complete trace of the following algorithm and count the number of steps you perform. a. Using the input x=4 and n-3 b. Using the input x = 2 and n = 7 d. What does this algorithm do? e. Write an iterative algorithm that does the same function. 2. Consider the following algorithm: Algorithm rec Function(val) if (val <1) print"... else return print val+">>" rec Function(val - 1) // print is used to signify screen output. Anything between // the quotation marks t is displayed as is and the + // concatenates the two parts on the screen Ile.g. if you have x=253 then print x+" // 253---253 +x will print print "<<"+ val return a. What is the base condition? b. How do the recursive calls reach the base condition? c. Show a complete trace of the following algorithm and count the number of steps you perform. a. Using the input val - 2 b. Using the input val = 8 3. Write a recursive algorithm to calculate the Fibonacci number (https://en.wikipedia.org wiki Fibonacci number). The Fibonacci number of an input value x is calculated as fib(x) = fib(x-1)+ fib(x-2); Also it is known that fib(0) = 0 and fib(1) = 1 For example if x = 4 then fib(4) = fib(3) +fib(2) fib(2) + fib(1) + fib(1) + fib(0) fib(1) +0 +fib(0) +fib(1) +fib(1) +fib(0) +1 +1 +0 =3

Answer rating: 100% (QA)

1a Base condition if n 1 return NULL 1b for any integer value of n 1 we reach to the nested if else ... View the full answer