This blog post is about a book titled “The Recursive Book of Recursion” written by Al Sweigart

What is Recursion ?

Summary

  • At its core, recursion depends on only two things: function calls and stack data structures
  • Most of the people find it difficult to understand recursion because recursion depends on the concept of stacks and introductory books do not mention or talk about stacks. Also the stacks are not seen in the code. It is something that the language does it for you at the background
  • All programming languages implement four features in their functions
    • functions have code that is run when the function is called
    • arguments are passed to the function when it’s called
    • functions return a return value
    • program remembers which line of code called the function and returns to it when the function finishes its execution
  • Every recursive program uses a call stack. Frame objects contain information about a single function call, including which line of code called the function, so the execution can move back there when the function returns
  • Frame objects are created and pushed on to the stack when the function is called. When the function returns, the frame object is popped off the stack
  • Typically a frame object has
    • return address, or the spot in the program where the execution should move when the function returns
    • arguments passed to the function all
    • set of local variables created during the function call
  • All recursive functions require at least one base case and at least one recursive case
  • Recursion is a useful technique, but recursion doesn’t automatically make code “better” or more “elegant”.

Further reading

Recursion vs. Iteration

Summary

  • Newbies get confused by recursion because there is usually a line where half of is executed before the recursive call and half of which after the recursive call returns
  • Between using iteration vs recursion for computing the factorial of a number, iteration is always better as the latter creates a lot of frame objects and takes up a lot of memory
  • recursive fibonacci implementation has three parts: before the first recursive call, after the first recursive call but before the second recursive call and after the second recursive call
  • Any recursive algo can be performed iteratively using a loop and a stack
  • You never need to use recursion. No programming problem requires recursion.
  • Recursion can provide new insights into how to think about our programming problem. Three features of a programming problem, make it suitable to a recursive approach
    • it involves a tree-like-structure
    • it involves backtracking
    • it isn’t so deeply recursive as to potentially cause a stack overflow
  • Recursion is the best approach for creating programming language compilers
  • Maze can be thought of as a tree
  • Interesting that you can implement any recursive function with a loop and a stack
  • List is a tree that has a branch on each node
  • File system is a tree
  • When you don’t have a tree structure or the need for back tracking, there is no need to use recursion
  • Tail call optimization - poster child is factorial(1001)
    • it prevents stack overflows
    • Normal recursive function cannot be straight away modified to incorporate tail call optimization
  • You can’t use tail call optimization in Python

Further reading

  • Loops vs recursion
    • Culture shock in 1940’s to suddenly find that recursion was very important
    • Historically you had packaged instructions that could be called when needed
    • One of the high level languages that introduced recursion is FORTRAN
    • Nature of FORTAN loop is almost like an assembly language
    • How did loops become powerful ? There is no reason to have a loop within a loop
    • Early FORTRAN would not allow more than 10 loops inside
    • C++ allows nested loops around 256
    • Multidimensional problems can be coped in nested loops as long as the multidimensional problems have about 256 dimensions
    • FORTRAN could not do recursion. There are no stack frames in FORTRAN. It has only one stack frame
    • ALGOL: code calls recursively
    • Not many things need recursion. You can do most of the problems with loops
    • Primitive recursive problems can be done via loops
    • Compilers need recursion
    • By 1960 there were enough users at user level, a modicum of recursion will be useful to have in any programming language
    • Ackermann’s function can only be done recursively and you cannot do recursively
  • Python Profilers

Classic Recursion Algorithms

Summary

  • Head tail technique for implementing recursive functions
    • This technique splits the recursive function’s array argument in two parts: the head(the first element of the array) and the tail( a new array including everything after the first element)
  • The key tell that our recursive function is unnecessary is that it never does any backtracking over the data it processes
  • Towers of Hanoi puzzle : classic CS problem that introduces recursion
  • Flood fill algorithm : The book solves the problem using recursion but this can be solved via DFS and BFS algorithms
  • The famous Ackermann’s function is mentioned. This is one of those fascinating functions that can be written recursively written, but the program for even simple arguments will take forever to compute.

Further reading

Backtracking and Tree Traversal Algorithms

Summary

  • In the case of tree traversal, the three questions about recursive algos ?
    • What is the base case? A leaf node
    • What argument is passed to the recursive function call ? Node to traverse to, whose child nodes will be the next nodes to traverse
    • How does this argument become closer to the base case ? There are no cycles in a DAG, so following the descendant nodes will always eventually reach a leaf node
  • Preorder tree traversal algorithms access a node’s data before traversing its child nodes.
    • traverses left nodes before right nodes, and bottom nodes before top nodes
  • Postorder tree traversal traverses a node’s child nodes before accessing the node’s data.
    • displays data in the left nodes before right nodes, and in bottom nodes before top nodes
  • Preorder and Postorder traversal: The names are a bit misnomer as nodes are always traversed in the same order; we go down the child nodes first as opposed to visiting the nodes in the each level before going deeper. The pre and post refer to when the node’s data is accessed: either before or after traversing the node’s children
  • Inorder tree traversal traverses the left child node, then accesses the node’s data, and then traverses the right child node
  • A simply connected maze also called a perfect maze contains no loops, every location is reachable from every other location and there are no isolated sections
  • Tree traversal algos can be used to solve mazes. One can use a DFS algo to quickly search mazes
  • A recursive method suits mazes as it naturally handles the “explore, forward, backtrack when struck” pattern

Further reading

Divide and Conquer Algorithms

Summary

  • Divide and conquer algorithms are those that split large problems into smaller subproblems, then divide those subproblems into ones that are smaller yet, until they become trivial to conquer.
  • Detailed description of the way quick sort works along with respective python and JavaScript codes
  • Detailed description of the way merge sort works along with respective python and JavaScript codes
  • Learned about Karatsuba algorithm that can be implemented via recursion. I had never come across this example before and hence felt nice coding up this algo. Even though the algo is easy to read and understand, coding it might need one to be careful to take care of all edge cases

Further reading

Permutations and Combinations

Summary

  • Whether it is permutations or combinations, with or without repetition, one can use recursion to get the enumeration of all possibilities. This chapter talks through various recursive algos that can be written to get the enumerations.
  • Generating powerset of a given set can be accomplished via recursion
  • Found this chapter a fun chapter to read and implement the code
  • Balanced parenthesis problem and its connection to Catalan numbers
  • After going through this chapter, I think one will get enough practice about writing recurrence relations involving problems where some sort of counting is needed

Memoisation and Dynamic Programming

  • Memoisation is the technique of remembering the return values from a function for the specific arguments supplied to it
  • DP is a computer programming technique that involves breaking a large problem into overlapping subproblems. The key different is that DP uses recursion with repeated recursive cases; these are the overlapping subproblems
  • There is no such thing as top-down recursion or bottom-up recursion. These are commonly used but incorrect terms. All recursion is already top-down, so top-down recursion is redundant. And no bottom-up approach uses recursion, so there’s no such things as bottom-up recursion
  • Not all functions can be memoised
  • If a function is deterministic and has no side effects, it’s known as a pure function. Only pure functions should be memoized
  • Python’s standard library has functools module with a function decorator named @lru_cache that automatically memoizes the function it decorates.
    • lru stands for least recently used cache replacement policy, meaning that the least recently used entry is replaced with new entries when the cache limit is reached.

Tail Call Optimization

  • A function is a tail call when it is a last thing the function does and the function returns the result of that call directly
1
2
3
4
5

# Tail call def f(x): return g(x) # Nothing left to do after calling g()

# Not a tail  call def f(x): return  1 + g(x) # Something  happens after calling
g()

  • Python does not support tail call optimization
  • What does TCO do?
    • Deletes current stack frame.
    • Reuses it for next recursive call.
    • Reduces space from O(n) ? O(1).
  • Why use it?
    • Safe for deep recursion.
    • Equivalent performance to loops.
    • Clear and functional-style code.
  • Python and TCO
    • CPython does NOT implement TCO.
    • Languages that do: Scheme, Haskell, OCaml, Scala, some JS engines.
  • The disadvantage of tail recursion is that it requires rearranging your recursive function so that the last action is returning the recursive call’s return value
  • There are a bunch of examples mentioned in this chapter that the author says will fail in Python as CPython does not support tail call optimization. However it is merely for instructive purpose I guess as it will give one a sense of what changes one needs to make a program in to something that compiler can do tail call optimization
  • Author says that tail recursion technique should never be used. Any recursive algo can be implemented with a loop and a stack.

Rest of the book

The first 200 pages of the book gives you all the necessary ammunition to understand various aspects of recursion. The second part of the book contains 5 different projects that one can work on so as to solidify one’s understanding about recursion

Takeaway

This is probably one of the first books that I have read where the author says that the entire subject of his book is overrated in Computer Science and then goes to write 300 pages on the subject. Like the author says, whatever you want to accomplish using recursion, you can use a loop and stack to get done. Hence should one really need to read this book ? My suggestion for you to look at this book from POV - How one can introduce a subject or concept in a pedagogical way, incrementally introducing one related concept after another and keep the readers engaged through out. The author does a great job of structuring each chapter with just enough examples, review questions and review exercises that you tend to walk away from the book appreciating the effort the author has put in to write this book. So, feel free to skip this book if all you are aiming is to understand recursion just enough to use it in a practical way. But if you are interested in understanding how one could actually write a 300 page book on recursion that keeps readers attention through out, then this book is worth a read. I think more than the book, the various links and resources mentioned at various points in the book make it a worthwhile read. It is a fun read and if your idea of fun is to read about something, implement it in your favorite programming language, then this book might be something that you can invest time and effort.