CSC148H5 Lecture Notes - Lecture 5: Sleeping People
Document Summary
Tracing recursion: bottom-up when tracing a given recursive function (evaluating the output of a given input), we recommend the following approach. Start tracing from the simplest cases (no recursive call) Trace the next-most complex case by plugging in known results of simpler cases. Keep doing this until you trace the required (most-complex) case. The bottom-up approach is convenient for tracing, but it is not how python (or other languages) actually runs a recursive program. The execution starts from the top-level function call, then makes deeper levels of recursive calls. In general, when function a calls function b, it"s like a go to sleep, b wakes up, finish the task, then return to a, then a wakes up and continue. The values needed by the sleeping people is remembered some region in memory. Note the order when a calls b, then b calls c last sleep, first wake up.