Prep 6: Module 6

Module Overview

Module Overview

Module Introduction

Module Introduction

Explicit Recursion

Explicit Recursion

Exercise: Recursive Factorial and Sum

Part 1: Introduction

Recursive Factorial and Sum: Introduction

Part 2: Demonstration of the debugger using factorial

Demonstration of the debugger using factorial

Part 3: The Exercise

  • In the exercises6 package of the exercises source folder, create

    • Sum.java as a Java class

    • SumTest.java as a JUnit test file

  • Complete both so that sum is computed as defined by the explicitly recursive formula:

    • sum(n) = sum(n-1) + n, if n > 0

    • sum(n) = 0, otherwise

  • Write some tests for sum and run the unit test file to make sure your function works.

Remember that you have to have a @Test directive above any unit test method, as shown in the video.

Part 4: Solution

Recursive Factorial and Sum: Solution

Exercise: Recursive Addition

Part 1: The Exercise

  • In the exercises6 package of the exercises source folder, complete the

    • Add.java

    • addTest.java

  • Complete both so that addition is computed as defined by the explicitly recursive formula:

    • add(x,y) = x, if y = 0
    • add(x,y) = add(x+1,y-1), otherwise
  • Write some more tests for add and run the unit test file to make sure your function works.

Remember that you have to have a @Test directive above any unit test method, as shown in the video.

  • Under what conditions on x and y does your method operate correctly?

  • How could you complete the addAll(x,y) method so it works for any x and y?

See the code, as a hint is given there.

Part 2: The Solution

Recursive Addition: Solution

Finding Recursive Substructure

Finding Recursive Substructure

Exercise: Recursion and Base Cases

Part 1: Introduction

Recursion and Base Cases: Introduction

Part 2: The exercise

Part 1

In the video, one possible explanation for human reproduction was given, namely that a woman is born with all of the babies already inside her that she would ever deliver. This idea is attributed to Anton von Leeuwenhoek who, as a lensmaker, greatly advanced the use of microscopes in studying biology. In terms of recursion and base cases, what is wrong with von Leeuwenhoek’s speculation?

Part 2

  • In the exercises6 package of the exercises source folder, find and open the FactorialNoBaseCase class.

  • Run the class as a Java Application.

  • What happens, and why?

Part 3: Solution

Recurstion and Base Cases: Solution

Roundtable: Method Execution using the Debugger

Video
Part 1
Part 2
Part 3
Part 4
Part 5
Part 6
Part 7

Example: Generating graph paper

Generating graph paper

Exercise: Generating graph paper

Part 1: Introduction

Generating graph paper: Introduction

Part 2: The exercise

  • In the exercises6 package of the exercises source folder, find and open the GraphPaper class.

  • Complete the class so that it produces a grid on the screen

  • Think about the recursive substructure of drawing a grid

  • Think about the base case(s)

Part 3: Solution

Generating graph paper: Solution

Substitution Model

Substitution Model

Roundtable: Substitution practice: factorial

Video
Part 1
Part 2
Part 3
Part 4

Roundtable: Tracing Recursion

Video
Part 1
Part 2
Part 3

Roundtable: More tracing recursion

Video
Part 1
Part 2
Part 3

Conclusion

Conclusion