1 of 19

�

Warm-up: 9/1

Given an integer,

a) How do you access the ones digit?

b) How do you access the tens digit?

c) How do you remove the ones digit of an int?

Example: 458

a) 8

b) 5

c) 458 -> 45

2 of 19

Warm-up #1a

iterative implementation

On a whiteboard with your partner:

Given a non-negative int n, compute the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).

count8(8) → 1

count8(818) → 2

count8(8818) → 4

public int count8(int n) {

3 of 19

�

Warm-up #1b

recursive implementation

On a whiteboard with your partner:

Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).

count8(8) → 1

count8(818) → 2

count8(8818) → 4

public int count8(int n) {

4 of 19

�

CodingBat > recursion-1 > count8

Check your code for both implementations.

5 of 19

�

charAt String method

What is the output? String str = "Bellaire"; System.out.println(str.charAt(0)); System.out.println(str.charAt(str.length()-1)); System.out.println('b' == str.charAt(0)); System.out.println(str.substring(1));

6 of 19

�

charAt String method

String str = "Bellaire"; System.out.println(str.charAt(0)); System.out.println(str.charAt(str.length()-1)); System.out.println('b' == str.charAt(0)); System.out.println(str.substring(1)); Output: B e false ellaire

7 of 19

�

Warm-up #2a

iterative implementation

Given a string, return a new string where all the 'x' chars have been removed. noX("xaxb") → "ab" noX("abc") → "abc" noX("xx") → "" public String noX(String str) {

8 of 19

�

Warm-up #2b

recursive implementation

Given a string, compute recursively a new string where all the 'x' chars have been removed. noX("xaxb") → "ab" noX("abc") → "abc" noX("xx") → "" public String noX(String str) {

9 of 19

�

CodingBat > recursion-1 > noX

Check your code for both implementations.

10 of 19

10

CodingBat > Recursion-1 > countX, changeXY, array220

Share implementations for countX and changeXY.

Yesterday, when we called on our recursive method array11, the initial call was made with index 0 and the parameter was incremented by 1 each subsequent call.

For strings, how do we change the parameter str for subsequent recursive calls after the initial call with str?

Go over homework

11 of 19

Why recursion?

Yesterday, we discussed how the recursive implementation of the fibonacci sequence was much less efficient than the iterative implementation.

Why would we use the recursive implementation then?

12 of 19

Why recursion?

Yesterday, we discussed how the recursive implementation of the fibonacci sequence was much less efficient than the iterative implementation.

Why would we use the recursive implementation then?

Divide and Conquer sorting algorithms --> merge sort, quick sort
Binary search
Tower of Hanoi problem
Implementing methods of various data structures

13 of 19

�

Tower of Hanoi

14 of 19

(aka Tower of Brahma or Lucas’ Tower)

3 posts
Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
No larger disk may be placed on top of a smaller disk.

Tower of Hanoi

15 of 19

Recall story about an Indian temple which contains a large room with three time-worn posts in it, surrounded by 64 disks.

Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time. According to the legend, when the last move of the puzzle is completed, the world will end.

How many years will it take to move 64 discs if each priests can move one disc per second?

�

Tower of Brahma

16 of 19

How many years will it take to move 64 discs if each priests can move one disc per second?

�

Tower of Brahma

17 of 19

How many years will it take to move 64 discs if each priests can move one disc per second?

2^64-1 ~ 6*10^11 years �(about 600 billion years - about 42 times the current age of the Universe)

�

Tower of Brahma

18 of 19

How can we think of this algorithm as recursive?

�

Tower of Brahma

19 of 19

CodingBat > Recursion-1 (complete online and then write solutions in IN) - submit on Hub - both recursive AND iterative implementation
count7
powerN
countHi
allStar

Homework