Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
4th Edition
ISBN: 9780134787961
Author: Tony Gaddis, Godfrey Muganda
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Videos
Textbook Question
Chapter 16, Problem 9PC
Efficient Computation of Fibonacci Numbers
Modify the application in Code Listing 16-18 by replacing the recursive method for computing Fibonacci terms with an iterative version and try to make it as efficient as possible. Modify the application so it outputs the elapsed time in both seconds and milliseconds. Finally, run the application and generate output showing the rime required to compute the terms of the sequence in positions 45, 46, 47, 48, 49, and 50. Comment on the results.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
1. Write a recursive method expFive(n) to compute y=5^n. For instance, if n is 0, y is 1. If n is 3,
then y is 125. If n is 4, then y is 625. The recursive method cannot have loops. Then write a
testing program to call the recursive method. If you run your program, the results should look like
this:
> run RecExpTest
Enter a number:
3
125
>run RecExpTest
Enter a number:
3125
2. For two integers m and n, their GCD(Greatest Common Divisor) can be computed by a
recursive function. Write a recursive method gcd(m,n) to find their Greatest Common
Divisor. Once m is 0, the function returns n. Once n is 0, the function returns m. If neither
is 0, the function can recursively calculate the Greatest Common Divisor with two
smaller parameters: One is n, the second one is m mod n. Although there are other
approaches to calculate Greatest Common Divisor, please follow the instructions in
this question, otherwise you will not get the credit. Meaning your code needs to follow
the given algorithm.
Then…
The solution must be recursive.
inputAndPrintReverse:Inputs integers from the user until the user enters 0, then prints the integers in reverse order. For this method, you may NOT use an array or any type of array structure, in other words, you may not use any structure to store the user input.
Fibonacci numbers are a sequence of integers, starting with 1, where the value of each number is the sum of the two previous numbers, e.g. 1, 1, 2, 3, 5, 8, etc. Write a function called fibonacci that takes a parameter, n, which contains an integer value, and have it return the nth Fibonacci number. (There are two ways to do this: one with recursion, and one without.)
Chapter 16 Solutions
Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
Ch. 16.1 - Prob. 16.1CPCh. 16.1 - Prob. 16.2CPCh. 16.1 - Prob. 16.3CPCh. 16.1 - Prob. 16.4CPCh. 16.2 - Prob. 16.5CPCh. 16.2 - Prob. 16.6CPCh. 16.2 - Prob. 16.7CPCh. 16.2 - If a sequential search is performed on an array,...Ch. 16.3 - Prob. 16.9CPCh. 16.3 - Prob. 16.10CP
Ch. 16.3 - Prob. 16.11CPCh. 16.3 - Prob. 16.12CPCh. 16.3 - Prob. 16.13CPCh. 16.3 - Prob. 16.14CPCh. 16.3 - Let a[ ] and b[ ] be two integer arrays of size n....Ch. 16.3 - Prob. 16.16CPCh. 16.3 - Prob. 16.17CPCh. 16.3 - Prob. 16.18CPCh. 16 - Prob. 1MCCh. 16 - Prob. 2MCCh. 16 - Prob. 3MCCh. 16 - Prob. 4MCCh. 16 - Prob. 5MCCh. 16 - Prob. 6MCCh. 16 - Prob. 7MCCh. 16 - Prob. 8MCCh. 16 - Prob. 9MCCh. 16 - Prob. 10MCCh. 16 - True or False: If data is sorted in ascending...Ch. 16 - True or False: If data is sorted in descending...Ch. 16 - Prob. 13TFCh. 16 - Prob. 14TFCh. 16 - Assume this code is using the IntBinarySearcher...Ch. 16 - Prob. 1AWCh. 16 - Prob. 1SACh. 16 - Prob. 2SACh. 16 - Prob. 3SACh. 16 - Prob. 4SACh. 16 - Prob. 5SACh. 16 - Prob. 6SACh. 16 - Prob. 7SACh. 16 - Prob. 8SACh. 16 - Prob. 1PCCh. 16 - Sorting Objects with the Quicksort Algorithm The...Ch. 16 - Prob. 3PCCh. 16 - Charge Account Validation Create a class with a...Ch. 16 - Charge Account Validation Modification Modify the...Ch. 16 - Search Benchmarks Write an application that has an...Ch. 16 - Prob. 8PCCh. 16 - Efficient Computation of Fibonacci Numbers Modify...
Additional Engineering Textbook Solutions
Find more solutions based on key concepts
7.13* For a bearing
DE = NUS 5 53’56 ”WT and angles to the right, compute the bearing of PG if angle
DEF 2 88°...
Elementary Surveying: An Introduction To Geomatics (15th Edition)
In the following exercises, write a program to carry out the task. The program should use variables for each of...
Introduction To Programming Using Visual Basic (11th Edition)
Passing arguments to base classes constructors solves the problem of selecting a base class constructor in inhe...
Starting Out with C++: Early Objects (9th Edition)
Show a snippet of PHP code for creating a recordset. Explain the meaning of the code.
Database Concepts (8th Edition)
If a method in a subclass has the same signature as a method in the superclass, does the subclass method overlo...
Starting Out with Java: From Control Structures through Objects (7th Edition) (What's New in Computer Science)
Figure 1-30 shows the Visual Studio IDE. What are the names of the four areas indicated in the figure? Figure 1...
Starting Out With Visual Basic (8th Edition)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- No plagarism! Correct and detailed answer ( code with comments and output screenshot if necessary)arrow_forwardWrite a recursive function that returns the smallest integer in an array. Write a test program that prompts the user to enter a list of five integers and displays the smallest integer.arrow_forwardCreate a class Recursion. It will have two static methods: removeX and countSubstring and write each function recursively. Recursion class removeX The removeX function will take a String as a parameter. It will return a new String that is the same as the original String, but with all “x” characters removed. This method will be case insensitive. countSubstring The countSubstring function will take two strings as parameters and will return an integer that is the count of how many times the substring (the second parameter) appears in the first string without overlapping with itself. This method will be case insensitive. For example: countSubstring(“catwoman loves cats”, “cat”) would return 2 countSubstring(“aaa nice”, “aa”) would return 1 because “aa” only appears once without overlapping itself. Create a Main class to test and run your Recursion class.arrow_forward
- Create a function that returns the nth catalan number. In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814-1894). For more info, check out the resource tab. Examples getCatalanNumber (0) → 1 getCatalanNumber (6) → 132 getCatalanNumber (8) 1430 Notes Inputs are zero and positive integers.arrow_forwardGiven the sequence, S2 = 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, … Write a RECURSIVE method called “sequence2” that takes a single int parameter (n) and returns the int value of the nth element of the sequence S2. You will need to determine any base cases and a recursive case that describes the listed sequence. Use the following code to test your answers to questions 3 and 4the output should print the two sequences given (S & S2): public class TestSequences { public static void main(String[] args) { for(int i = 0; i < 10; i++) { System.out.print(sequence(i) + " "); // 2, 4, 6, 12, 22, 40, 74, 136, 250, 460 } System.out.println(); for(int i = 0; i < 10; i++) { System.out.print(sequence2(i) + " "); // 1, 2, 4, 5, 7, 8, 10, 11, 13, 14 } } // *** Your method for sequence here *** // *** Your method for sequences2 here *** } // end of TestSequences classarrow_forwardThe following recursive method get Number Equal searches the array x of 'n integers for occurrences of the integer val. It returns the number of integers in x that are equal to val. For example, if x contains the 9 integers 1, 2, 4, 4, 5, 6, 7, 8, and 9, then getNumberEqual(x, 9, 4) returns the value 2 because 4 occurs twice in x. public static int getNumberEqual(int x[], int n, int val) { if (n< 0) ( return 0; } else { if (x[n-1) == val) { return getNumberEqual(x, n-1, val) +1; } else { return getNumber Equal(x, n-1, val); } // end if ) // end if } // end get Number Equal Demonstrate that this method is recursive by listing the criteria of a recursive solution and stating how the method meets each criterion.arrow_forward
- Using JAVA Recursive Power Method Write a method called powCalthat uses recursion to raise a number to a power. The method should accept two arguments: The first argument is the exponentand the second argument is the number to be raised(example”powCal(10,2)means2^10). Assume that the exponent is anonnegative integer. Demonstrate the method in a program called Recursive (This means that you need to write a program that has at least two methods: mainand powCal. The powCal method is where you implement the requirements above and the main method is where you make a method call to demonstrate how your powCalmethod work).arrow_forwarddo in javaarrow_forwardWrite a recursive method that returns thelargest integer in an array. Write a test program that prompts the user to enter alist of eight integers and displays the largest element.arrow_forward
- Here we will create a method to find the smallest value in an array: We provided the code for you to start, Main is done, you need to create minFinder function, o First do it with loops Create another function minFinder_recursive, and use recursive function to create the code to find the min value (you may add more functions/methods as needed) Write the Pseudocode (https://en.wikipedia.org/wiki/Pseudocode) for BOTH functions and do a time analysis in Big-O for both (This step is really important) For the pseudocode, you do not need to be super detailed but in steps by steps tell us how your code works. The Sample Pseudocode will be shown in class oSubmit it in PDF. import java.util.Random; // this creates randon for our program public class App { public static int minfinder (int[] arr) { int index = 0; //YOUR CODE GOES HERE 1/ you have to do two ways, once with loops, once with Recusive (For recursive you need more functions or methods, so create them) //once you find the minimum…arrow_forwardJava Program: Recursive Method There are n people in a room where n is an integer greater then or equal to 2. Each person shakes hands once with every other person. What is the total number of handshakes in the room? Write a recursive method to solve this problem with the following header:public static int handshake(int n)where handshake(n) returns the total number of handshakes for n people in the room. To get you started if there are only one or two people in the room, then:handshake(1)=0handshake(2)=1arrow_forwardJava: Write a recursive method that finds and returns the sum of the elements of an int array. Also, write a program to test your method.arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
1.1 Arrays in Data Structure | Declaration, Initialization, Memory representation; Author: Jenny's lectures CS/IT NET&JRF;https://www.youtube.com/watch?v=AT14lCXuMKI;License: Standard YouTube License, CC-BY
Definition of Array; Author: Neso Academy;https://www.youtube.com/watch?v=55l-aZ7_F24;License: Standard Youtube License