Introduction

It is time to deepen our knowledge of recursion. You have already encountered this powerful principle in Programming 1 (if you need a refresher, consult the O1 material), and written basic recursive programs. In this chapter we will review that knowledge, and extend it by introducing some new concepts.

Recursion can allow you to write very concise Scala code, and is a staple technique of functional programming. However, not only functions can be defined recursively but also data structures. Usually, such data structures are also most naturally manipulated with recursive functions. In this chapter we will study two basic recursively defined data structures:

• Linked lists. This is a classic data structure and corresponds to the List class in Scala.

• Symbolic arithmetic expressions. This is an instance of a very common tree data structure.

Then we will be putting our new knowledge to the test by implementing a search problem recursively, and conclude with a note about hard problems.