[PDF] [PDF] Chapter 12 - Recursion - Lehman College City University of New

[PDF] Chapter 12 - Recursion - Lehman College City University of New

30 jan 2016 · Activity 12 5 1: Writing a recursive method for factorial: First write the base case, then add the recursive case Start public static int nFact(int N) {

[PDF] 16 Recursion - UNC Computer Science

Once we define the problem in this way, we can use recursion to solve it The general form of a recursive algorithm is: if (base case 1) return solution for base 

[PDF] Building Java Programs - Washington

recursive case: more complex occurrence of the problem that cannot Write a recursive method pow accepts an integer base and 5 An optimization Notice the following mathematical property: 312 Example: printBinary(12) prints 1100 return false; } // recursive case String middle = s substring(1, s length() - 1);

[PDF] Recursion Recursion

10 nov 2015 · Write a recursive version of this method (that calls itself) – Solve the problem without using any loops 8 A basic case • What are the cases to 

[PDF] Recursion and Recursive Backtracking - Fas Harvard

printSeries(n1 + 1, n2); } } • The base case stops the recursion, because it doesn' t make another call to the method Recursive Problem-Solving (cont )

[PDF] Recursive Function

case • Each recursive algorithm must have at least one base case, as well as the general (recursive) case Writing a recursive function to find n factorial 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 info 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28

[PDF] Recursion We teach recursion as the first topic, instead of new

base case Fibn = Fibn-1 + Fibn-2 for n > 1 recursive case 0, 1, 1, 2, 3, 5, 8, 13, 21, 4 Turn recursive definition into recursive function Factorial: 0 = 1 base case 12 Creating a recursive method Task: Write a method that removes blanks

[PDF] 22/02/2017 1 To Understand Recursion Recursion – Real Life

22 fév 2017 · Base case: 7 1-7 10 slide 13 □ How Java (or, how do we write/develop recursive methods?) Frames for methods sum main method in the system 12 public static int sum(int n) { Fibonacci sequence: 0 1 1 2 3 5 8 13

[PDF] 23 Recursion

1 2 3 Recursion 3 Overview What is recursion? When one function calls itself directly or indirectly Why learn •base case: Prove it for some specific N (usually 0 or 1) 1 + 3 + 5 + 7 + 9 = 1 converges to base case gcd(p, q) = gcd(3x, 2x) = x 12 Euclid's Algorithm GCD How to write simple recursive programs?

[PDF] 12.6.1: writing a recursive math method.

[PDF] 1200 stimulus check app

[PDF] 1200 stimulus check do i have to pay it back

[PDF] 1200 stimulus check do you have to pay back

[PDF] 1200 stimulus check pay back next year

[PDF] 1200 stimulus check payback irs

[PDF] 1200 stimulus check second round date

[PDF] 12000 btu to ton ac

[PDF] 1223/2009

[PDF] 123 go cast bella

[PDF] 123 go cast kavin real name

[PDF] 123 go cast lily

[PDF] 123 go cast names

[PDF] 123 go challenge 100 layers

[PDF] 123 go challenge eat it or wear it

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 1 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print

Chapter 12 - Recursion

Section 12.1 - Recursion: Introduction

An algorithm is a sequence of steps for solving a problem. For example, an algorithm for making lemonade is: Some problems can be solved using a recursive algorithm. A recursive algorithm solves a problem by breaking that problem into smaller subproblems, solving these subproblems, and combining the solutions. An algorithm that is defined by repeated applications of the same algorithm on smaller problems is a recursive algorithm. The mowing algorithm consists of applying the mowing algorithm on smaller

Figure 12.1.1: Algorithms are like recipes.

Figure 12.1.2: Mowing the lawn can be broken down into a recursive process.

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 2 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print pieces of the yard. At some point, a recursive algorithm must describe how to actually do something, known as the base case. The mowing algorithm could thus be written as:

Mow the lawn

If lawn is less than 100 square meters

Push the lawnmower left-to-right in adjacent rows

Else

Mow one half of the lawn

Mow the other half of the lawn

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 3 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print

Section 12.2 - Recursive methods

A method may call other methods, including calling itself. A method that calls itself is a recursive method.

Participation

Activity

P

12.1.1: Recursion.

Which are recursive definitions/algorithms?

#QuestionYour answer 1

Helping N people:

If N is 1, help that person.

Else, help the first N/2 people, then help the second N/2 people. True False 2

Driving to the store:

Go 1 mile.

Turn left on Main Street.

Go 1/2 mile.

True False 3

Sorting envelopes by zipcode:

If N is 1, done.

Else, find the middle zipcode. Put all zipcodes less than the middle zipcode on the left, all greater ones on the right. Then sort the left, then sort the right. True False

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 4 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print Each call to countDown() effectively creates a new "copy" of the executing method, as shown on the right. Returning deletes that copy. The example is for demonstrating recursion; counting down is otherwise better implemented with a loop.

Participation

Activity

P

12.2.1: A recursive method example.

public class CountDownTimer { public static void countDown(int countInt) { if (countInt == 0) {

System.out.println("GO!");

else {

System.out.println(countInt);

countDown(countInt-1); return; public static void main (String[] args) { countDown(2); return; 21GO!
public static void main (String[] args) {

CountDown(2);

return; public static void countDown(int countInt) { if (countInt == 0) {

System.out.println("GO!");

else {

System.out.println(countInt);

countDown(countInt-1); return; public static void countDown(int countInt) { if (countInt == 0) {

System.out.println("GO!");

else {

System.out.println(countInt);

countDown(countInt-1); return; public static void countDown(int countInt) { if (countInt == 0) {

System.out.println("GO!");

else {

System.out.println(countInt);

countDown(countInt-1); return; Start countInt: 2countInt: 1countInt: 0

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 5 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print

Participation

Activity

P

12.2.2: Thinking about recursion.

Refer to the above countDown example for the following. #QuestionYour answer 1 How many times is countDown() called if main() calls

CountDown(5)?

2 How many times is countDown() called if main() calls

CountDown(0)?

3

Is there a difference in how we define the

parameters of a recursive versus non-recursive method? Answer yes or no.

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 6 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print

Section 12.3 - Recursive algorithm: Search

Consider a guessing game program where a friend thinks of a number from 0 to 100 and you try to

guess the number, with the friend telling you to guess higher or lower until you guess correctly. What

algorithm would you use to minimize the number of guesses? A first try might implement an algorithm that simply guesses in increments of 1:

Is it 0? Higher

Is it 1? Higher

Is it 2? Higher

This algorithm requires too many guesses (50 on average). A second try might implement an algorithm

Challenge

Activity

C

12.2.1: Calling a recursive method.

Write a statement that calls the recursive method backwardsAlphabet() with parameter startingLetter. Run

System.out.println(currLetter);

else {

System.out.print(currLetter + " ");

backwardsAlphabet(--currLetter); return; public static void main (String [] args) { char startingLetter = '-'; startingLetter = 'z'; /* Your solution goes here */ return; 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
22

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 7 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print that guesses by 10s and then by 1s:

Is it 10? Higher

Is it 20? Higher

Is it 30? Lower

Is it 21? Higher

Is it 22? Higher

Is it 23? Higher

This algorithm does better but still requires about 10 guesses on average: 5 to find the correct tens

digit and 5 to guess the correct ones digit. An even better algorithm uses a binary search. A binary search algorithm begins at the midpoint of the range and halves the range after each guess. For example:

Is it 50 (the middle of 0-100)? Lower

Is it 25 (the middle of 0-50)? Higher

Is it 37 (the middle of 25-50)? Lower

Is it 31 (the middle of 25-37).

After each guess, the binary search algorithm is applied again, but on a smaller range, i.e., the algorithm is recursive.

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 8 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print A recursive method is a natural match for the recursive binary search algorithm. A method guessNumber(lowVal, highVal) has parameters that indicate the low and high sides of the guessing range. The method guesses at the midpoint of the range. If the user says lower, the method calls guessNumber(lowVal, midVal). If the user says higher, the method calls guessNumber(midVal + 1, highVal).

Participation

Activity

P

12.3.1: Binary search: A well-known recursive algorithm.

mid Figure 12.3.1: A recursive Find() carrying out a binary search algorithm. import java.util.Scanner; public class NumberGuessGame { public static void guessNumber(int lowVal, int highVal) {

Scanner scnr = new Scanner(System.in);

int midVal = 0; // Midpoint of low..high char userAnswer = '-'; // User response midVal = (highVal + lowVal) / 2; // Prompt user for input System.out.print("Is it " + midVal + "? (l/h/y): "); userAnswer = scnr.next().charAt(0); if ((userAnswer != 'l') && (userAnswer != 'h')) { // Base case: found number

System.out.println("Thank you!");

Start 0100
(31)50 050
25
2550
37
2537
31
Guess middleHalve windowGuess middleHalve windowGuess middleHalve windowGuess middleCorrect

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 9 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print else { // Recursive case: split into lower OR upper half if (userAnswer == 'l') { // Guess in lower half guessNumber(lowVal, midVal); // Recursive call else { // Guess in upper half guessNumber(midVal + 1, highVal); // Recursive call return; public static void main(String[] args) { // Print game objective, user input commands System.out.println("Choose a number from 0 to 100.");

System.out.println("Answer with:");

System.out.println(" l (your num is lower)");

System.out.println(" h (your num is higher)");

System.out.println(" any other key (guess is right)."); // Call recursive function to guess number guessNumber(0, 100); return;

Choose a number from 0 to 100.

Answer with:

l (your num is lower) h (your num is higher) any other key (guess is right).

Is it 50? (l/h/y): l

Is it 25? (l/h/y): h

Is it 38? (l/h/y): l

Is it 32? (l/h/y): l

Is it 29? (l/h/y): h

Is it 31? (l/h/y): y

Thank you!

Participation

Activity

P

12.3.2: Binary search tree tool.

The following program guesses the hidden number known by the user. import java.util.Scanner; public class NumberGuess { public static void Find(int low, int high) {

Scanner scnr = new Scanner(System.in);

int mid = 0; // Midpoint of low..high char answer = '\0'; mid = (high + low)/2;

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 10 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print mid = (high + low)/2;

System.out.print("Is it " + mid + "? (l/h/y): ");

answer = scnr.next().charAt(0); if( (answer != 'l') && (answer != 'h') ) { // Base case: System.out.println("Thank you!"); // Found number! else { // Recursive case: Guess in // lower or upper half of range if (answer == 'l') { // Guess in lower half

Find(low, mid); // Recursive call

else { // Guess in upper half

Find(mid+1, high); // Recursive call

return; public static void main (String[] args) { System.out.println("Choose a number from 0 to 100.");

System.out.println("Answer with:");

System.out.println(" l (your num is lower)");

System.out.println(" h (your num is higher)");

System.out.println(" any other key (guess is right).");

Find(0, 100);

return;

Current functionFunction code

→main() public static void main (String[] args) { System.out.println("Choose a number from 0 to 100.");

System.out.println("Answer with:");

System.out.println(" l (your num is lower)");

System.out.println(" h (your num is higher)");

System.out.println(" any other key (guess is right).");

Find(0, 100);

return;

1/30/16, 11:03 AMLehman College City University of New York CMP 167 Spring 2016: Programming in Java

Page 11 of 44https://zybooks.zyante.com/#/zybook/LehmanCMP167Spring2016/chapter/12/print The recursive method has an if-else statement. The if branch ends the recursion, known as the base case. The else branch has recursive calls. Such an if-else pattern is common in recursive methods.

Search is commonly performed to quickly find an item in a sorted list stored in an array or ArrayList.

Consider a list of attendees at a conference, whose names have been stored in alphabetical order in

an array or ArrayList. The following quickly determines whether a particular person is in attendance.

Figure 12.3.2: Recursively searching a sorted list. import java.util.Scanner; import java.util.ArrayList; public class NameFinder { /* Finds index of string in vector of strings, else -1.

Searches only with index range low to high

Note: Upper/lower case characters matter

quotesdbs_dbs31.pdfusesText_37