A Recursive Algorithm for Fibonacci Numbers. procedure fibonacci(n: nonnegative integer) if n = 0 then return 0 else if n = 1 then return 1 else return fibonacci(n - 1) + fibonacci(n - 2) {output is fibonacci(n)} An Iterative Algorithm for Computing Fibonacci Numbers. procedure iterative fibonacci(n: nonnegative integer) if n = 0 then return 0 else x: = 0 y: = 1 for i:= 1 to n - 1 z: = x + y x:= y y:= z return y {output is the nth Fibonacci number} Consider Algorithm 7 on page 365 which finds the nth Fibonacci number, f_n, recursively, for n greaterthanorequalto 0. Let T(n) be the number of additions done by the algorithm to compute f_n. Do the following: (a) Give a recursive definition for T(n). (b) Use Strong Induction to establish that T(n) = f_n + 1 - 1, for n greaterthanorequalto 0. (c) Determine the number of additions done by Algorithm 7 to compute f_10 and compare this to the number of additions done by Algorithm 8. A Recursive Algorithm for Fibonacci Numbers. procedure fibonacci(n: nonnegative integer) if n = 0 then return 0 else if n = 1 then return 1 else return fibonacci(n - 1) + fibonacci(n - 2) {output is fibonacci(n)} An Iterative Algorithm for Computing Fibonacci Numbers. procedure iterative fibonacci(n: nonnegative integer) if n = 0 then return 0 else x: = 0 y: = 1 for i:= 1 to n - 1 z: = x + y x:= y y:= z return y {output is the nth Fibonacci number} Consider Algorithm 7 on page 365 which finds the nth Fibonacci number, f_n, recursively, for n greaterthanorequalto 0. Let T(n) be the number of additions done by the algorithm to compute f_n. Do the following: (a) Give a recursive definition for T(n). (b) Use Strong Induction to establish that T(n) = f_n + 1 - 1, for n greaterthanorequalto 0. (c) Determine the number of additions done by Algorithm 7 to compute f_10 and compare this to the number of additions done by Algorithm 8