Study the Fibonacci number sequence in the following forms: (1) iterative (sequential), (2) recursive, (3) and closed form solution. 1) Examine the theoretical measure of time complexity of each. a) Using theory compare the number of operations and time taken to compute Fibonacci numbers recursively versus that needed to compute them iteratively. b) How many prime Fibonacci numbers are there, and how many can you find? c) Find the smallest Fibonacci number > 1,000,000 d) Find the smallest Fibonacci number > 1,000,000,000

Study the Fibonacci number sequence in the following forms: (1) iterative (sequential), (2) recursive, (3) and closed form solution. 1) Examine the theoretical measure of time complexity of each. a) Using theory compare the number of operations and time taken to compute Fibonacci numbers recursively versus that needed to compute them iteratively. b) How many prime Fibonacci numbers are there, and how many can you find? c) Find the smallest Fibonacci number > 1,000,000 d) Find the smallest Fibonacci number > 1,000,000,000

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter15: Recursion

Section: Chapter Questions

Problem 17PE

See similar textbooks

Similar questions

(a) Devise a recursive algorithm using design by induction for computing n2 where theinput to the algorithm n is a nonnegative integer. Hint: Use the fact that (n + 1)2 =n2 + 2n + 1.(b) Discuss the running time requirements of your algorithm.
(a) The Fibonacci sequence can also be seen in hurricanes prediction. The shape takes in the form of a spiral, it can be in a nesting process and repeated into infinity. It is called the logarithmic spiral, and it abounds in nature. The Fibonacci sequence of numbers, “Fn”, is defined using the recursive relation. Fibonacci sequence of numbers can be computed as follows: Fn = Fn-1+Fn-2 If the 12th and 13th terms in the hurricane prediction sequence are 89 km/hour and 144 km/hour, analyze the value of the 15th, 16th, and 17th hurricane speed by using the Fibonacci formula as stated above.
Given three sequences of length m, n, and p each, you are to design and analyze an algorithm to find the longest common subsequence (LCSS) for the three sequence. Is it possible to use dynamic programming to find the LCSS between the three sequences? If yes, provide recursive solution to the above problem.
Find the solution and draw the recursion trace for the execution of function Recursive (3). Please circle your answer. Algorithm Recursive (x) : Input: Integer x Output: Integer d if x > 7 d = 5 else if x = 7 d = 3 else d = Recursive (x + 3) + Recursive (x + 1) returnd
Develop two algorithms, one based on a loop structure and the other on a recursive structure, to print the daily salary of a worker who each day is paid 2.5 times the previous day’s salary (starting with one penny for the first day’s work) for a 30-day period. What problems relating to number storage are you likely to encounter if you implement your solutions on an actual machine?
Differentiate between Recursion and Iteration and when to use them. (b) Give two (2) examples of problems that can be solved using Recursion.
Compare the number of operations and time taken to compute Fibonacci numbers recursively versus that needed to compute them iteratively
An arithmetic sequence a starts 84,77,... Define a recursively Define a for the n th term
6. Recursive Algorithms i. Give a recursive algorithm (not a formula!) for finding na where n is a positive integer and a is a real number. Prove that your algorithm is correct.
Recursion can be direct or indirect. It is direct when a function calls itself and it is indirect recursion when a function calls another function that then calls the first function. To illustrate solving a problem using recursion, consider the Fibonacci series: - 1,1,2,3,5,8,13,21,34...The way to solve this problem is to examine the series carefully. The first two numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2.Recursive functions need a stop condition. Something must happen to cause the program to stop recursing, or it will never end. In the Fibonacci series, n < 3 is a stop condition. The algorithm to use is this: 1. Ask the user for a position in the series.2. Call the fib () function with that position, passing in the value the user entered.3. The fib () function examines the argument (n). If n < 3…
List three types of recursion to reach a termination of recursions with a high-level description and a specific algorithm falling into each type.
Question 3 a) Iteration and recursion are two very fundamental concepts underlying things we do in computing. (i). Distinguish between the terms Iteration and Recursion in the context of solving problems in business, science or engineering. (ii). Using practical examples in business, science or engineering, explain reasons why people still use recursion to solve problems even-though iteration is more efficient. b) Describe how a Savings and Loans Company can use singly-linked lists to keep track of customers that its Susu collectors (or mobile bankers) have won for the company over the last 2 months; and draw a suitable diagram (with hypothetical data) to illustrate your answer. c) In many fields of human endeavour, we use stacks on daily basis. Provide and explain four practical examples where we use stacks in real life.