Unit 5: Recursion
Often considered one of the more conceptually difficult concepts within the field of Computer Science, recursion - the act of a function invoking itself - is a powerful and relevant tool for any Computer Scientist. In this unit, we will take an in-depth look at recursion, learning the recursive steps, the role that recursion plays in common data structures, and what happens inside the computer when a recursion function is invoked. By the end of this unit, you will recognize situations that require recursion and be able to apply it appropriately.
Note: Recursion can be a difficult concept for some students new to the field of Computer Science. This anxiety is best resolved through the use of an example. For this module, we will employ the use of recursion to write a program to express the "factorial" function. This straightforward example will give the student an overview of all the major components of recursion.
Completing this unit should take you approximately 5 hours.
Upon successful completion of this unit, you will be able to:
- demonstrate an understanding of the general uses of recursion in programming, including its utility in solving programming problems; and
- demonstrate an understanding of the basic search algorithms that are recursive in nature and how they are used in programming.
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: Applying Recursion
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 Structures
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: Recursive 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: Examples of Recursion
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.
5.2: Recursive Algorithms
- Recursion is a decomposition/composition problem solving technique. With reference to the typical programming process, recursion applies to design and to coding. Recursive algorithms are used in designing, and recursive implementations are used in coding. Usually recursion in design originates from recursive data structures, because they are generic and apply to many types of problems or tasks. For example, trees are a widely useful data structure, used in games, decision making, analysis, etc. Recursive implementations tend to pertain to specific problems or tasks. However, if there are similar problems, a recursive implementation may be applicable to those similar problems. Scan the resource material for Unit 5 looking at the examples used to explain and illustrate recursion, noting how you might use them as problem solving resources for future problems you may want to solve.