================================================================================ Tail Recursion Notes One potential problem when executing a recursive function is a stack overflow, which is something you've probably come across when writing recursive functions in other languages like Java or C. The runtime stack is a data structure that keeps records of information for every function that is currently executing. For example, in C, every program starts executing a main function, and main may call a function foo, which may in turn call bar. While bar is executing the runtime stack looks like | | | | | | |--------| | bar() | |--------| | foo() | |--------| | main() | |--------| At all times, the top of the stack holds information for the function that is currently executing, including the function's inputs. When the function completes and produces a return value, that function's record is popped off the stack and execution resumes where it left off in the previous function. Whenever a function is called, a new record for the call is pushed onto the stack. The stack dynamically grows and shrinks during program execution, and since memory is finite, it might completely fill up so that execution is unable to proceed. Such a stack overflow may be a symptom of an infinite recursion. For example, consider the following function that attempts to sum the first n integers: # let rec sum_n_bad n = n + sum_n_bad (n-1);; Since there's no base case provided, the recursion continues infinitely. # sum_n_bad 1;; Stack overflow during evaluation (looping recursion?). We can fix this by only recursing when n is positive: # let rec sum_n n = if n <= 0 then 0 else n + sum_n (n-1);; This is great, but passing in large values of n result in a stack overflow, because the recursion depth becomes too large. # sum_n 1000000;; Stack overflow during evaluation (looping recursion?). This example shows that, even though we've avoided infinite recursion, there is still a limit to how many outstanding recursive calls can be on the stack at once. Tail recursion is a technique that allows a recursive function to use only _constant_ amount of space on the stack instead of an amount _linear_ in the number of calls. The idea is that if making a recursive call is the last thing that a function does before returning its result, then there does not need to be a separate stack record for each invocation. Consider, a tail-recursive implementation of the same function: # let rec sum_n_tr acc n = if n <= 0 then acc else sum_n_tr (n+acc) (n-1);; Notice that whenever a recursive call to sum_n_tr for (n-1) returns, that value is returned immediately as the return value of sum_n_tr for n. We also use an additional parameter called acc (or accumulator) which is used to incrementally accumulate the final result that will eventually be returned. So in the inductive case, we add n to the running total stored in acc, and when we finally get to the base case n <= 0, we simply return the running total that we've accumulated in acc. # sum_n_tr 0 1000000;; - : int = -363189984 Awesome, no stack overflow! The result is surprising, however, but that's because of an integer overflow, not the recursion depth... :-) So in general, whenever all recursive calls to a function occur as the final result of the function, the function is said to be tail-recursive, and the OCaml compiler is able to perform an optimization that allows the code at runtime to only use a _single_ record on the stack frame. Think about why this is possible. One thing to note is that sum_n is probably more readable and elegant than solution, but sum_n_tr is more efficient (runs faster) and does not run out of stack space on large inputs. There is often a tradeoff between simplicity and efficiency, but for practical purposes, it is usually preferable to write functions as tail-recursive if possible, especially because the resulting functions are typically still very readable in OCaml.