Programming in C · topic
Base and recursive cases, stack frames, tracing prints placed before and after recursive calls, call trees, recursion depth, recurrences for the number of calls, memoisation, tail recursion and mutual recursion.
Base case and recursive case, what a stack frame holds, a stack snapshot for a function that prints before and after its recursive call, a tracing routine based on the call tree, prints placed between two recursive calls (in-order), static counters shared by all frames and the unspecified order trap in return f(n - 1) + c, value-returning recursion (digit sum, digit reversal, fast power) and recursion that never reaches its base case.
A partial preview of the top of the sheet. The full sheet is in the Programming in C cheat sheet pack.
Separate recurrences for the value and for the number of calls, the call tree of naive Fibonacci with call and addition counts, two-call trees and Towers of Hanoi with closed forms, recursion depth versus total calls, the effect of memoisation on call counts, tail recursion and its loop form (C does not guarantee tail-call elimination), and mutual recursion with a prototype. Every count is compiled or computed by a script.
A partial preview of the top of the sheet. The full sheet is in the Programming in C cheat sheet pack.
