COMPSCI 61A Study Guide - Final Guide: List Comprehension, Linked List, System On A Chip

• School: Berkeley
• Department: Computer Science
• Course: COMPSCI 61A
• Professor: John Denero

Document Summary

Tail recursion should only save your memory, not change the answer you get. Stuff all the work (result of a recursive function needed later) into a helper function: store value in function call itself instead of saving value and adding (or any math) it with each recursive call. Bad: sum + (helper n -1: no adding outside of recursive call. Additive factorial has big o (n2: n + (n 1) + (n 2) frames are not equal to runtime frames: space complexity, runtime: how long it takes function to terminate. Cascade function: cascade (0, 3: call (descending) Call (descending: call (descending, return (ascending) Example2: sum_reverse (modify a tree such that each element becomes the sum of its children) def sum_reverse (t): Don"t need a base case cause won"t error without; if empty, the list comprehension just won"t execute cause t. branches is empty.