Computers are powerful, but they have limits. Because of this, part of a programmer's job is to manage a computer's resources efficiently—if a programmer writes a program that is too inefficient, the computer will run out of resources attempting to execute it. There are two broad ways a program can be inefficient: space and time. Space is the amount of "scratch paper" the computer requires to carry out a program. Time is the amount of time required before the computer finishes running a program. In the following sections, we will examine both of these dimensions in detail.
First, we will take a look at space. An inefficient program may take up too much space to run, leading the computer to crash. We will examine what causes this and how we may prevent it through a specific type of recursion—tail recursion.
Next, we will consider time. Some programs may run longer than than the lifespan of the universe. (For example, the best programs we know to find a perfect solution to Chess.) We will learn how to identify such programs, and more generally, introduce and practice a method in which to measure how time-efficient our programs are.
Lastly, we will also describe another new type of recursion—tree recursion. Utilizing tree recursion in our programs allows us to tackle problems that we previously didn't have the tools to solve. We will particularly focus on what the costs and benefits this new technique brings.
You can check out additional readings in the book and the lecture notes. Each section of the lesson has more specific book links so that you can check out in case something is unclear.