AP Computer Science A -- Recursion

Matryoshka Doll | Explaining Recursion | Tower of Hanoi | Merge Sort | Review | Resources

The Matryoshka Doll

A matryoshka doll, also known as a Russian nesting doll, Stacking dolls, or Russian doll, is a set of wooden dolls of decreasing size placed one inside another. The name "matryoshka", literally "little matron", is a diminutive form of Russian female first name "Matryona".

A set of matryoshkas consists of a wooden figure which separates, top from bottom, to reveal a smaller figure of the same sort inside, which has, in turn, another figure inside of it, and so on until finally a tiny, solid figure is reached.

Matryoshkas are used metaphorically, as a design paradigm, known as the "matryoshka principle" or "nested doll principle". It denotes a recognizable relationship of "object-within-similar-object" that appears in the design of many other natural and crafted objects.

Assignment: Question for Thought 10.1

Directions: After watching the video of the Matryoshka Doll. Write up a summary of what is happening with the Matryoshka Doll. Submit your response of ~100 words to the itsLearning textbox. Do not attach a separate document and proofread your response before submitting.

Explaining Recursion

To do list

Recursion is when a method calls itself. The key to being able to program recursively is to be able to think recursively. Recursion is a programing technique that can be used to solve a problem in which a solution to the problem can be found by making subsequently smaller iterations of the same problem. When used correctly, it can be an extremely elegant solution to a problem. Any problem that can be solved recursively can be solve iteratively.

Choose recursion rather than looping when the problem you are trying to solve can be solved by repeatedly shrinking the problem down to a single, final simple problem. You should avoid recursion when the iterative solution is simpler and more easily understand and programmed. Recursion has many method calls and is not always easy to follow.

Assignment: Recursion Basics Video Check

Directions: After watching and studying the video on Recursion Basics, take the short video check in itsLearning.

Base Case

One method can call another method. With recursion, a method calls itself. If you think about that, after the method was invoked the first time, the program would never end because the method would continue to call itself forever. However, if the method had some kind of trigger that told it when to stop calling itself, then it would be a good recursive method.

The base case of a recursive method is a comparison between a parameter of the method and a predefined value strategically chosen by the programmer. The base case comparison determines whether or not the method should call itself again. Each time the recursive method calls itself and the base case is not satisfied, the method temporarily sets the call aside before making a new call to itself. This continues until the base case is satisfied. When there is finally a call to the method that makes the base case true (satisfied), the method stops calling itself and starts the process of returning a value for each of the previous method calls. Since the calls are placed on a stack, the returns are executed in the reverse order of how they were placed. This order is known as last-in, first-out (LIFO), which means that the last recursive call made is the first one that returns a value.

Every recursive method has two distinct parts:

If you write a recursive method and forget to put in a base case, or your subsequent calls to the method do not get you closer to the base case, you will probably cause infinite recursion, which will result in a stack overflow error.

The Towers of Hanoi

The Tower of Hanoi puzzle was invented in the 1880s by Edouard Lucas, a French mathematician. It is a favorite of computer scientists because its solution is an excellent demonstration of recursion.

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

The Tower of Hanoi solution has exponential complexity, which is very inefficient. Yet the implementation of the solution is incredibly short and elegant. To read more about the program logic behind Towers of Hanoi or to see the code, visit the article, Program for Tower of Hanoi by Rohit Thapliyal.

Assignment: Question for Thought 10.2

Directions: Tell me about recursion. Is recursion the same as iteration? Why or why not? Give one example of recursion in the real world. Submit your response of ~100 words to the itsLearning textbox. Do not attach a separate document and proofread your response before submitting.

Merge Sorts

A merge sort is a recursive sort. The merge sort algorithm divides the list to be sorted into smaller sublists, recursively sorting each sublist, then combining the sublists into their final sorted list. In the merge sort algorithm, the base case of the recursion is a list of one item.

Recursion Trace Examples

Assignment: Recursion Practice Worksheet

Directions: Download the Recursion Practice Worksheet. To trace a recursive call, write out each call of the method with the value of the parameter. When the base case is reached, replace each method call with its result. This will happen in reverse order.

Follow your instructor's instructions for submitting the worksheet after it is complete.

Tail Recursion

Tail recursion: is when the recursive call of a method is made at the last executable step of the method. A recursive function is tail recursive when recursive call is the last thing executed by the function. The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function's stack frame is of no use.

Assignment: Unit 10 Review Worksheet

Directions: Complete the review worksheet in itsLearning.


Quiz created by Shannon Anderson-Rush with GoConqr Flash Card Deck created by sarush with GoConqr