Unit 5 Study Guide and Review: Recursion
5a. Demonstrate an understanding of the general uses of recursion in programming, including its utility in solving programming problems
- What is recursion? What are data recursion and algorithm recursion?
- Recursion is a repetitive algorithm. What other algorithm can be used to accomplish the same purpose?
- What category of problem solving technique does recursion belong to?
- Name the parts of recursion.
Always review the framing text, which gives you the big picture concepts. The resources add details and examples that elaborate on the big picture and present examples that illustrate the concepts.
Recursion is easy to define, but hard to understand. "Recursive Definitions" gives a mathematical definition of recursion. "Recursion", from 13:00-15:40, introduces "divide and conquer" type of algorithms and illustrates them with recursion. When you review this video, pay close attention to its use in describing a problem and in describing a solution. Can you give an example of each use? The rest of the video, from 15:40 to the end, presents examples (tower of Hanoi, exponentiation, palindrome, and Fibonacci). The use of the program call stack, its building up until the base case is reached, and its unwinding until the original problem case is reached, is explained. "Notes on Recursion" is a set of notes that go into detail for the ideas presented in the "Recursion" video.
"Recursion (in Computer Science)" links recursion in Computer Science to mathematical induction in mathematics. This article is a technical discourse on recursion, covering recursive data, recursive functions, types of recursion, including tail recursion, comparison to iteration, and complexity.
5b. Demonstrate an understanding of the basic search algorithms that are recursive in nature and how they are used in programming
- Searching is inherently a step by step or 'piece by piece' iterative approach, and, is naturally, implementable using recursion.
- Recursion is a design choice and, as such, should be used based on the resources it will use (i.e. cost and time) compared to iteration.
- Does recursion have state, or is it stateless?
Our study, above, focused on two steps of a divide and conquer algorithm. "Divide and Conquer Methods" adds the third step. What is it? Review the video from 3:30-5:20. The rest of the video presents important and frequently used recursive algorithms, for sorting and searching. Consideration of complexity (cost of storage and execution time) is a major concern for algorithms that are widely used for large amounts of data.
Note that at 29:40, problem-solving algorithms are listed (brute force, guess and check, successive approximation, divide and conquer). What sort is examined in this video?
To fully understand recursion, we need to study many examples, such as those in "Programming via Java: Recursion", "C++ Recursion example", "Python Recursion examples". The first of these three resources walks through the call stack for an example. Since each call is local, it does not change the state of the application program which is solving a program using divide and conquer via recursion, and, we can conclude that recursion is stateless.
Unit 5 Vocabulary
This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.
Try to think of the reason why each term is included. Why are exceptions included? Are exceptions a divide and conquer solution? Do exceptions use the call stack?
- Base case
- Design process
- Divide and conquer
- Exceptions
- Inductive step and Composition step
- Fibonacci
- Hash function
- Iteration
- Merge sort
- Mathematical induction
- Programming process
- Recursion
- Recursive data
- Recursive algorithm
- Recursive problem
- Recursive solution
- Tail recursion
- Tower of Hanoi