• 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?

      • Recursive Definitions Page

        Read this article to learn the basics of recursion.


      • Recursion Page

        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

      • Divide and Conquer Methods Page

        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

      • Recursion in Java Page

        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.

      • Recursion in C++ Book

        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

      • Notes on Recursion Page

        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-Recursive Functions Page

        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.

      • Explicit vs. Recursive Programming Page

        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.



      • Recursive Rights and Wrongs Page

        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.

      • MergeSort: A Graphical Recursive Explanation Page

        This video interpretes recursion using stack visualization. Notice how memory-use expands and contracts as the process evolves.

      • Translating Between Recursive and Explicit Rules for Numeric Sequences Page

        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++

        • 6.5.2: Examples in Java

      • Unit 6 Assessment

        • Unit 6 Assessment Quiz
          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.