Chapter 22 Further Reading: Recursion

Books

  • Wirth, N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. Wirth's masterwork uses Pascal throughout and covers recursion with characteristic clarity. Chapter 3 on recursive algorithms is particularly relevant.

  • Abelson, H. & Sussman, G. J. (1996). Structure and Interpretation of Computer Programs, 2nd ed. MIT Press. The first chapter develops recursion as a fundamental concept using Scheme, offering a different perspective than the Pascal approach. Freely available at mitpress.mit.edu/sites/default/files/sicp/index.html.

  • Roberts, E. S. (1986). Thinking Recursively. John Wiley & Sons. A short, focused book entirely about recursive thinking, with examples in Pascal. If recursion still feels mysterious after this chapter, Roberts's book will demystify it.

  • Hofstadter, D. R. (1979). Godel, Escher, Bach: An Eternal Golden Braid. Basic Books. A Pulitzer Prize-winning exploration of self-reference, recursion, and formal systems across mathematics, art, and music. Not a programming book, but a profound meditation on the recursive structures that underlie intelligence itself.

Online Resources

  • Free Pascal Documentation: Procedures and Functions. freepascal.org/docs-html/ref/refch14.html. Official reference for function declarations, forward declarations, and calling conventions in Free Pascal.

  • Visualgo: Recursion Tree Visualizer. visualgo.net/en/recursion. Interactive visualization of recursive call trees for factorial, Fibonacci, and other algorithms.

  • The Recursion Fairy (CS concept). A pedagogical metaphor where you imagine a "recursion fairy" who magically solves the recursive sub-problem. You only need to trust the fairy and handle the base case. Search "recursion fairy" for various explanations of this teaching technique.

Historical Context

  • McCarthy, J. (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." Communications of the ACM 3(4), 184–195. The paper that introduced Lisp, the first language to make recursion a primary control mechanism. Understanding why Lisp chose recursion over iteration deepens appreciation for both approaches.

  • Dijkstra, E. W. (1960). "Recursive Programming." Numerische Mathematik 2(1), 312–318. An early and influential analysis of recursion in programming, by the same Dijkstra who argued against GOTO statements.

Topics for Further Exploration

  • Memoization and Dynamic Programming (Chapter 25). The fix for exponential recursive redundancy. If this chapter left you frustrated by naive Fibonacci, Chapter 25 provides the cure.

  • Recursive Descent Parsing. The mutual recursion example in Section 22.7 is a simplified recursive descent parser. Compiler construction courses develop this into a complete parsing technique for programming languages.

  • Fractal Geometry. Mandelbrot's The Fractal Geometry of Nature (1982) explores the mathematical foundations of the fractals we drew in Case Study 2.

  • Backtracking Algorithms. N-Queens (Exercise D.6), Sudoku solvers, and maze generators all use recursive backtracking — a technique where you make a choice, recurse, and undo the choice if the recursion fails.