5.1: Definition
Read this article about recursion.
5.1.1: Divide and Conquer
This video discusses recursion as a divide and conquer problem solving technique, a design technique, and a programming technique.
5.1.2: Applications to Programming
These notes expand on the topic of recursion as a way to decompose problems into subproblems. They also apply to decomposing data structures into sub-substructures. Identifying the recursive problem or data structure and their implementation in a program require a thorough understanding of the programming process. Some implementation topics are pointed out, including reentrant code, recursion vs. iteration (loops), relation of recursion to the functional and imperative programming paradigms, and common mistakes in programming recursion.
Tail-recursion is a type of recursion where the last statement executed is the recursive call and, therefore, there are no instructions after that call. When the return from the recursive call is made, the calling function terminates, in which case the return address to the calling function is not necessary. Some compilers and some languages do not save the return address back to the recursive calling function and translate tail recursion into machine instructions for a loop, which saves space on the stack and execution time. However, implementation of source tail recursion using machine code for a loop is compiler and/or language dependent.
5.1.3: Recursive Structure
This video delves deeper into divide and conquer algorithms. Some of these algorithms are recursive. Recursion is a way of decomposing a problem into smaller or simpler problems of the same type. We have discussed the base subproblem and the inductive subproblem when applying recursion. A third consideration is composition -- namely, how will simpler subproblems be composed into a solution to the larger problem? Sometimes the decomposition is easy but the composition is hard; sometimes the reverse holds.
The lecturer employs complexity to compare algorithms -- how does the number of steps in a solution to a problem grow as n grows, where n is the number of operations or data elements involved in the inductive step? Formally, that complexity approach is called Big 'O'. The lecturer presents two examples. The message of the video is that designing and implementing algorithms involves tradeoffs: decomposition vs composition tradeoff (merge sort example), and tradeoff of storage space vs. run-time (hash function example).
Most of the concepts you encounter in programming languages are related to reuse of algorithms or designs and implementations. These are categorized by complexity (for example the merge sort example has n log n complexity), which helps us decide their appropriateness for certain kinds of problems. The lecture closes with enhancements to the examples using exceptions and assertions (pre and post conditions), covered in unit 4 of our course. They help us handle different expectations that may arise in reusing the algorithms.
5.1.4: Steps
This resource goes into recursion for Java in detail. It goes over several Java examples. It states that the steps of induction can be implemented using either recursion or loops; for a particular program, one implementation may be more effective or efficient than the other. Given a program that implements recursion, stepping through the program statement by statement helps to understand the details of how recursion works at run-time. The run-time system makes use of an internal stack that records the run-time states of a recursive function. Diagrams of the stack are given that show the changes in state of the method during run-time, that is, the pushing of the state when the method is called and the popping of the stack when the method has finished executing. The diagrams help you to understand recursive behavior.
5.1.5: Recursion Examples
In these lectures we use Python, which is an easy-to-use procedural and object-oriented language, but our focus will not be on the syntax of the language. Rather, our focus is the concept of recursion, the requirements for the program (i.e., the statement of the problem), the design of the program, the semantics of the program (this is the stage in which we don't worry too much about the syntax of Python - knowing Java and C++ enables you to learn Python easily), and the verification of the program implementation (we do this by stepping through the program and running several test cases).
Note that the term verification refers to the correctness: the code running without errors and the code correctly implementing the design. Validation refers to the satisfaction of the requirements for the program: the requirements accurately reflecting problem or task the program is to perform, the design satisfying the requirements, and the code satisfying the requirements.