1 of 89

​

Recursion

Method Calling Itself

​

Unit 10

1

1

TClark

No Transitions

TClark

TClark

2 of 89

Activity with

Recursive

Directions

2

2

TClark

TClark

TClark

3 of 89

  1. On a half sheet of paper, draw a large equilateral triangle.
  2. Draw three dots, each on the center of the edges.
  3. Connect the dots to form a triforce.
  4. Repeat the procedure (the dots & triforce); with each of the 3 non-center inner triangles that have side lengths than 2cm.

Activity - Sierpinski's Triangle

TClark

TClark

4 of 89

Activity - Sierpinski's Triangle (TClark ver)

TClark

TClark

5 of 89

Recursion

Definition

5

5

TClark

TClark

TClark

6 of 89

Recursion is a technique where one method will call itself, usually with a parameter that is a smaller data set.

Recursion is used to break a complex problem into a simpler problem of the same type which eventually leads to the ending condition.

​

Two parts:

  • Base case: base condition with return value
  • Pattern with recursive call

Recursion

TClark

TClark

7 of 89

Two parts:

  • Base case: base condition with return value
  • Pattern with recursive call

Recursion Two Parts

TClark

TClark

8 of 89

Return the answer for the known case.

  • Sometimes there can be a few known cases, but most of the time you want just one case.

if(base_case_condition)�{� return known_solution;�}

Base Case

TClark

TClark

9 of 89

Return a call to the same method with a smaller data set, in an equation

The smaller data set should trend/go towards the base case.

else �{� return n ~math~ sameMethod(n-1);�}

​

Assume that the recursive call works correctly, i.e. sameMethod(n-1) will return the correct value of whatever it should be.

~math~ depends on the problem

Pattern

TClark

TClark

10 of 89

​

if(base_case_condition)�{� return known_solution;�}�else �{� return n ~math~ sameMethod(n-1);�}

Full Example

TClark

TClark

11 of 89

When creating or working with recursive functions, keep in mind these two questions:

  • What is the base case with result?
  • What is the pattern with recursive call?

Two Questions

TClark

TClark

12 of 89

Sierpinski's Triangle

Example

12

12

TClark

TClark

TClark

13 of 89

  • What is the base case?
    • side length < 2cm → done
  • What is the pattern?
    • draw a triangle using midpoints of the sides (to make it a triforce)
    • then make a sierpinski triangle in the top triangle
    • then make a sierpinski triangle in the right triangle
    • then make a sierpinski triangle in the left triangle

Sierpinski's Triangle Questions

TClark

TClark

14 of 89

Sierpinski's Triangle: recursive directions

TClark

TClark

15 of 89

Factorial

Example n!

15

15

TClark

TClark

TClark

16 of 89

  • What is the base case?
    • 0! → 1
  • What is the pattern?
    • Multiply the current int by the factorial of the next smaller int
    • n! → n * (n-1)!

Factorial Questions n!

TClark

TClark

17 of 89

public int factorial(int n)

{

if(n == 0)

{

return 1;

}

else

{

return n * factorial(n-1);

}

}

Factorial Method

TClark

TClark

18 of 89

Identify Parts

Practice

18

18

TClark

TClark

TClark

19 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Product - Two Parts

TClark

input less than or equal to 1 → return 1

multiply input to the product call with next smaller integer: n * product(n-1)

​

TClark

20 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Mystery1 - Two Parts

TClark

The else to the if statement:

if x / 10 != 0

​

it will only call the recursion if the conditional is true

  • print the ones digit
  • call mystery1 with the ones digit removed: (x/10)
  • print the ones digit

TClark

21 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Mystery2 - Two Parts

TClark

input is zero → return 1

multiply three times the mystery2 call with next smaller integer

TClark

22 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Mystery3 - Two Parts

TClark

input is zero → return 1

multiply five times the mystery3 call with next smaller integer and subtract that from two

TClark

23 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Fibonacci - Two Parts

TClark

input is 0 → return 0

input is 1 → return 1

add finacci call with next smaller integer to the fibonacci call with integer two smaller

TClark

24 of 89

Factorial

Tracing

24

24

TClark

TClark

TClark

25 of 89

public int factorial(int n)

{

if(n == 0)

{

return 1;

}

else

{

return n * factorial(n-1);

}

}

Factorial (product) Method

TClark

TClark

26 of 89

5!

5 * 4!

4 * 3!

3 * 2!

2 * 1!

1 * 0!

1 ← base case: 0! is 1

factorial(5)

TClark

TClark

27 of 89

5!

5 * 4!

4 * 3!

3 * 2!

2 * 1!

1 * 1

factorial(5)

TClark

TClark

28 of 89

5!

5 * 4!

4 * 3!

3 * 2!

2 * 1!

1

factorial(5)

TClark

TClark

29 of 89

5!

5 * 4!

4 * 3!

3 * 2!

2 * 1

factorial(5)

TClark

TClark

30 of 89

5!

5 * 4!

4 * 3!

3 * 2!

2

factorial(5)

TClark

TClark

31 of 89

5!

5 * 4!

4 * 3!

3 * 2

factorial(5)

TClark

TClark

32 of 89

5!

5 * 4!

4 * 3!

6

factorial(5)

TClark

TClark

33 of 89

5!

5 * 4!

4 * 6

factorial(5)

TClark

TClark

34 of 89

5!

5 * 4!

24

factorial(5)

TClark

TClark

35 of 89

5!

5 * 24

factorial(5)

TClark

TClark

36 of 89

5!

120

factorial(5)

TClark

TClark

37 of 89

120

factorial(5)

TClark

TClark

38 of 89

120

factorial(5)

TClark

TClark

39 of 89

Reverse String

Example

39

39

TClark

TClark

TClark

40 of 89

  • What is the base case?
    • empty string (length is 0) → empty string: ""
    • if the parameter is an empty string, return an empty string
  • What is the pattern?
    • last letter concatenated to the reverse of all the letters before it
    • reverse("clark") → "k" + reverse("clar")

Reverse String Questions

TClark

TClark

41 of 89

public String reverse(String str)

{

if(str.length() == 0)

{

return "";

}

return str.substring(str.length()-1) +

reverse( str.substring(0, str.length()-1) );

}

​

Reverse Method

TClark

TClark

42 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

a + reverse("cl")

l + reverse("c")

c + reverse("")

"" ← base case

reverse("clark")

TClark

TClark

43 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

a + reverse("cl")

l + reverse("c")

c + ""

reverse("clark")

TClark

TClark

44 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

a + reverse("cl")

l + reverse("c")

c

reverse("clark")

TClark

TClark

45 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

a + reverse("cl")

l + c

reverse("clark")

TClark

TClark

46 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

a + reverse("cl")

lc

reverse("clark")

TClark

TClark

47 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

a + lc

reverse("clark")

TClark

TClark

48 of 89

reverse("clark")

k + reverse("clar")

r + reverse("cla")

alc

reverse("clark")

TClark

TClark

49 of 89

reverse("clark")

k + reverse("clar")

r + alc

reverse("clark")

TClark

TClark

50 of 89

reverse("clark")

k + reverse("clar")

ralc

reverse("clark")

TClark

TClark

51 of 89

reverse("clark")

k + ralc

reverse("clark")

TClark

TClark

52 of 89

reverse("clark")

kralc

reverse("clark")

TClark

TClark

53 of 89

kralc

reverse("clark")

TClark

TClark

54 of 89

kralc

reverse("clark")

TClark

TClark

55 of 89

Base Condition

MUST WORK

55

55

TClark

TClark

TClark

56 of 89

If the base condition is not reached, i.e. the smaller data set skips it, then it could result in an infinite recursion error which will crash the program: � stack overflow

  • Common problem: if the base condition is checking to see when the parameter is zero, but the recursive calls subtract two
    • if the initial number is odd, it will skip zero

Base Condition MUST WORK

TClark

TClark

57 of 89

public int mystery(int n)

{

if(n == 0)

{

return 10;

}

else

{

return n + mystery(n-2);

}

}

​

What happens if you call: mystery(5)?

Recursion Problem → stack overflow

TClark

TClark

58 of 89

mystery(5)

5 + mystery(3)

3 + mystery(1)

1 + mystery(-1)

-1 + mystery(-3)

-3 + mystery(-5)

-5 + mystery(-7)

-7 + mystery

​

pattern skips 0 &�keeps going on�forever until the�computer crashes

mystery(5)

TClark

TClark

59 of 89

Recursive Practice:

M1 Call Stack

59

59

TClark

TClark

TClark

60 of 89

Mystery1 - Call Stack

TClark

TClark

61 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Mystery1 - Two Parts

TClark

The else to the if statement:

if x / 10 != 0

​

it will only call the recursion if the conditional is true

  • print the ones digit
  • call mystery1 with the ones digit removed: (x/10)
  • print the ones digit

TClark

62 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

123…mystery1(54) …

1234…mystery1(5) …

12345… BASE CASE …

now do second part

TClark

Mystery1 - Call Stack

TClark

63 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

123…mystery1(54) …

1234…mystery1(5) …

12345 …5

TClark

Mystery1 - Call Stack

TClark

64 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

123…mystery1(54) …

1234…mystery1(5) …

123455

TClark

Mystery1 - Call Stack

TClark

65 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

123…mystery1(54) …

123455 …4

TClark

Mystery1 - Call Stack

TClark

66 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

123…mystery1(54) …

1234554

TClark

Mystery1 - Call Stack

TClark

67 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

1234554 …3

TClark

Mystery1 - Call Stack

TClark

68 of 89

mystery1(54321)

1…mystery1(5432) …

12…mystery1(543) …

12345543

TClark

Mystery1 - Call Stack

TClark

69 of 89

mystery1(54321)

1…mystery1(5432) …

12345543 …2

TClark

Mystery1 - Call Stack

TClark

70 of 89

mystery1(54321)

1…mystery1(5432) …

123455432

TClark

Mystery1 - Call Stack

TClark

71 of 89

mystery1(54321)

123455432 …1

TClark

Mystery1 - Call Stack

TClark

72 of 89

mystery1(54321)

1234554321

TClark

Mystery1 - Call Stack

TClark

73 of 89

1234554321

TClark

Mystery1 - Call Stack

TClark

74 of 89

1234554321

TClark

Mystery1 - Call Stack

TClark

75 of 89

Recursive Practice:

M2 Call Stack

75

75

TClark

TClark

TClark

76 of 89

Mystery2 - Call Stack

TClark

TClark

77 of 89

  • What is the base case with result?

​

​

​

  • What is the pattern with recursive call?

Mystery2 - Two Parts

TClark

input is zero → return 1

multiply three times the mystery2 call with next smaller integer

TClark

78 of 89

mystery2(4)

3 * mystery2(3)

3 * mystery2(2)

3 * mystery2(1)

3 * mystery2(0)

1 ← BASE CASE

TClark

Mystery2 - Call Stack

TClark

79 of 89

mystery2(4)

3 * mystery2(3)

3 * mystery2(2)

3 * mystery2(1)

3 * 1

TClark

Mystery2 - Call Stack

TClark

80 of 89

mystery2(4)

3 * mystery2(3)

3 * mystery2(2)

3 * mystery2(1)

3

TClark

Mystery2 - Call Stack

TClark

81 of 89

mystery2(4)

3 * mystery2(3)

3 * mystery2(2)

3 * 3

TClark

Mystery2 - Call Stack

TClark

82 of 89

mystery2(4)

3 * mystery2(3)

3 * mystery2(2)

9

TClark

Mystery2 - Call Stack

TClark

83 of 89

mystery2(4)

3 * mystery2(3)

3 * 9

TClark

Mystery2 - Call Stack

TClark

84 of 89

mystery2(4)

3 * mystery2(3)

27

TClark

Mystery2 - Call Stack

TClark

85 of 89

mystery2(4)

3 * 27

TClark

Mystery2 - Call Stack

TClark

86 of 89

mystery2(4)

81

TClark

Mystery2 - Call Stack

TClark

87 of 89

81

TClark

Mystery2 - Call Stack

TClark

88 of 89

81

TClark

Mystery2 - Call Stack

TClark

89 of 89

END

89

89

TClark

​

​

​

​

Created by: TClark

License & Credit

​

TClark

​

​

​

​

Created by: TClark

License & Credit

​

TClark