Join Peggy Fisher for an in-depth discussion in this video Recursion, part of Foundations of Programming: Discrete Mathematics.
- View Offline
- Recursion is the process of self-referential definitions. A famous recursion problem, the Towers of Hanoi, describes a legend where several Buddhist monks created three large pegs in a room. They placed 64 discs on one of the pegs in ascending size order. Their objective was to move all 64 discs from one peg to another. But there is a catch. They could only move one disc at a time, and they can never place a larger disc on top of a smaller disc.
Moving one disc at a time, this would take roughly 585 billion years. The process to solve the puzzle is a perfect example of recursion. When dealing with recursive functions, there are two things that need to be determined. First, the base case, which is the last action to solve a problem. And second, the recursive process. With the tower, the base case is when the last piece is placed on the new peg.
Here is a model of the Towers of Hanoi with only four discs. This model makes solving the problem easier, since every other disc is a different color. To arrive at the base case, I must always put the disc on a peg, alternating the colored discs. A key to solving this puzzle is recognizing that it can be solved by breaking the problem down into smaller problems, and then further breaking those problems down into even smaller problems until a solution is reached.
Factorials are also solved with recursion. In mathematics, the factorial of a number is written as a number followed by an exclamation point, such as five exclamation point, which is read five factorial. This represents the product of all integers between five and zero. So, five factorial equals five times four times three times two times one times one, which is equal to 120.
To show the recursion, I first identify the base case, which, in this case, is zero factorial, which equals one. Next, we identify the recursive case, which is n times n minus one factorial until n reaches zero. In expanded form, it would look like this. N factorial is equal to n times n minus one times n minus two, until you get to three times two times one.
A fun recursive pattern involves dominoes. I'll set up the base case, just one domino, and then add a new domino in front of the previous, so that if it falls, it will knock down the one behind it. Remember, when working with recursion, identify the base case and then the recursive portion of the problem.
This course relies on an open-source SML (standard machine language) library to demo the concepts behind discrete math. Peggy Fisher shows you how to manipulate sets of data, write proofs and truth tables, analyze data sequences, and visualize data using graph theory. Challenges at the end of every chapter allow you to test your knowledge. By the end of the course, you should be able to make the leap from theory to using discrete math in practice: saving time and resulting in code that's cleaner and easier to maintain in the long run.
- Real-world discrete math
- Objects as sets
- Set notation and operations
- Standard machine language (SML) setup
- Working with data types, strings, and functions in SML
- Analyzing data sequences
- Writing truth tables
- Identifying and evaluating predicates
- Validating arguments
- Writing proofs: subset, conditional, and biconditional proofs
- Visualizing data with graphs
- Advanced discrete math techniques