COMPSCI 61A Lecture : Tree Recursion
22
COMPSCI 61A Full Course Notes
Verified Note
22 documents
Document Summary
Def cascade(n): if n < 10: print n else: print n cascade(n//10) print n. Any statement can appear before or after recursive call. Tree recursion: tree shaped processes when execute body of recursive function makes more than one call to that function def fib(n): if n == 1: return 0 elif n == 2: return 1 else: return (fib(n-2) + fib(n-1)) Computational process of fib evolves into tree structure. Use @trace [from ucb import trace] to follow. Repetition in tree recursive computation fib called on same argument multiple times. # partitions of pos int n using parts up to size m is # ways n can be expressed as sum of pos int up to parts m in increasing order. Solve two simpler problems: partition ( 2, 4) partition ( 6, 3)
