ABSTRACT
The algorithms followed the declarative programming paradigm, which focuses on what programs compute from a high-level point of view. This chapter examines recursive programs from a low-level perspective, illustrating how they work, by showing the order in which instructions are carried out. It describes several representations of the thought process regarding how recursive programs work, some of which are known as "mental models" of recursion. It introduces recursion trees, which are popular graphical representations of the sequence of calls carried out by recursive programs. Among their benefits, they are useful for debugging, help evaluate functions, allow programmers to visualize the computational (time and space) complexity of a recursive program, and can characterize the types of recursion covered so far. The chapter covers their relationship with the program stack, which is a data structure that programs use to implement general subroutine (i.e., method) calls. Memoization is closely related to dynamic programming, which is an important algorithm design technique.
