From the course: Programming Foundations: Discrete Mathematics

Recursion

From the course: Programming Foundations: Discrete Mathematics

Start my 1-month free trial

Recursion

“

- 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.

Contents