Unit 6: 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. In this unit, we will take an in-depth look at recursion, learning how to develop recursive processes, the role that recursion plays in common data structures, and what happens inside the computer when a function is invoked recursively. By the end of this unit, you will recognize situations that require recursion and be able to apply it appropriately.
Recursion can be a difficult concept for students new to computer science. If you feel anxious, your best best is to use examples. In this unit, we will use recursion to write a program to express factorials (N!). This straightforward example will give you an overview of all the major components of recursion. Many good examples are also illustrated through the unit, particularly in the sections that discuss the Towers of Hanoi and the Merge Sort.
Completing this unit should take you approximately 7 hours.
Upon successful completion of this unit, you will be able to:
- demonstrate the general uses of recursion in programming, including its utility in solving programming problems;
- show how several basic search algorithms are recursive in nature and the ways they are used in programming;
- explain explicit programming and compare it to recursive programming; and
- evaluate situations to determine whether recursive programming would be appropriate.
6.1: What is Recursion?
Read this article to learn the basics of recursion.
Recursion is a problem-solving technique for decomposition and recomposition. In the typical programming process, recursion applies to both design and coding. Recursive algorithms are used in designing, and recursive implementations are used in coding. Usually, recursion in design comes 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 that are used in games, decision-making, analysis, and more. 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. This video introduces recursion as a "divide and conquer" problem-solving technique, a design technique, and a programming technique.
6.2: 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 is true.
In this video, the lecturer uses 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 takeaway here is that designing and implementing algorithms involves tradeoffs: decomposition versus composition (as seen in the merge sort example), and tradeoff of storage space versus run-time (as seen in the hash function example).
Most of the concepts you encounter in programming languages are related to reusing algorithms or designs and implementations. These are categorized by complexity; for example, the merge sort example has n log n complexity. This helps us decide their appropriateness for certain kinds of problems. The lecture closes by showing how you can enhance the examples using exceptions and assertions (pre- and post-conditions), which were covered in Unit 4 of our course. They help us handle different exceptions that might arise when reusing algorithms.
6.3: Recursive Steps
This resource goes into recursion in detail using Java, and goes over several examples. 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. Be sure to review the diagrams.
The principles of recursion are the same, regardless of the language used for implementation. This chapter views the topic through the lens of C++. There are a fair number of examples and visualizations. Read through these at a minimum. You might find the exercises useful since the application of a principle is an aid to your understanding. Read Chapter 5 in this book on C++.
6.4: 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.
From an academic perspective, recursion seems rather elegant and it requires less code to run. Plus, many algorithms are easier to express recursively than explicitly (without recursion). There is much to recommend recursion. However, expressing an algorithm recursively is not always the right thing to do. For one thing, it is difficult to predict the amount of memory and time consumed by a recursive implementation. Many applications in industry require tight and known runtimes. Memory availability is limited as well. Every time a recursive call is made, more memory is occupied, which takes additional time.
An example is an experience where two offerings of code were made to solve a particular industrial problem. One was recursive. The other was explicit. When tested on the equipment upon which the code was to run, the recursive version ran out of memory for even the simplest case. The explicit case operated fine well-beyond the most complex cases that could be produced in reality. It is interesting to note that the recursive version had only six lines of code, whereas the explicit version had 300 lines of code. One can argue as to which was more understandable to the human reader or which was more "elegant". But, one can not argue as to the effectiveness of the codes in the situation within which they had to operate.
The next few pages will introduce this area of discussion to you and provide a few illustrations. You will notice a number of call trees. These portray the relationship of functions and their data that come to reside in memory as a recursive process proceeds. Pay particular attention to this topic since a problem is not "solved" until it operates in the stark reality of industrial situations.
For more on this area of thinking, read through these two discussion threads.The author is convinced that, if you want to ever consider yourself an experienced programmer, you should be trying to understand cases where recursion is not an appropriate design. His article is intended to help you gain that understanding as quickly as possible. His examples are written in Javascript. You will note the closeness of the syntax to Java.
This video interpretes recursion using stack visualization. Notice how memory-use expands and contracts as the process evolves.
It is worth examining various numeric sequences and their implementation via recursive and non-recursive approaches.
6.5: Examples of Recursion
These examples are in addition to the ones shown earlier in this unit.
6.5.1: Examples in C/C++
Discussed in this video is the conversion of a mathematical theorem to a recursive process. Then that process is explained step-by-step for given input values.
There is a complete description of the coding process in this video. There is also a quick view of memory-pointer management within a recursive process.
There is a complete description of the coding process in this video.
6.5.2: Examples in Java
Offers a discussion on the recursive processing of binary trees. A code walk-through is included. Material begins at Time Marker 4:31.
Unit 6 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.