Lab 7: Recursion and Recursive Backtracking

Task 0: Recursion Review, The basics

Task 1: Designing Recursive Methods

In class we’ve talked a lot about how recursive methods work, how to understand them, and how to trace them out. With lab we’ll continue talking a bit about how to design recursive functions or how to break down problems to fit the recursive mold.

Review the solutions from some of the Challenge problems.

Task 2: Recursive Backtracking

In lecture yesterday we saw how we could use the technique of recursive backtracking to solve the N-Queens problem. We can use the same technique for determining how to color states on a map.

What are the common characteristics of these two problems?

Understanding how recursive backtracking works in these two scenarios will help you implement a recursive backtracking solution for the Sudoku problem of ps5.

To understand how, let’s review and make sure we understand the full recursive backtracking solution to the N-queens problem.

Task 3: Challenge (if you have not completed from prior lab)

Write a recursive method to solve each of the following:

1. The greatest common denominator is a common problem in mathematics. Given two positive numbers, what is the largest factor that divises both integers. Write a recursive function that takes in two integers and finds the greatest common denominator. (Hint: Look up Euclids algorithm)

2. Find the product of the integers from 1 through n (this is called the factorial function). If n is zero, return 1. Write a recursive method that takes in an integer and computes (and returns) the factorial of that integer.

   What happens if you try to compute the factorial of a very large number? Why do you think this is the case?

3. Count the number of times a specific number occurs in an array of integers. Write a recursive method that takes in an array of integers and some number n and returns the number of times n occurs in the array. Note we did something simiar in class.

4. Find the minimum element in an array of integers. Write a recursive method that takes in an array of integers and returns the minimum integer in the array.

   Hint: Think through the parameters you need to pass to the last couple of methods.