EECS 280 Lecture Notes - Lecture 20: Tail Call, Call Stack

• School: U of M
• Department: Electrical Engineering And Computer Science
• Course: EECS 280
• Professor: DeOrio

Document Summary

The idea of recursion is that you keep repeating and repeating it. Yes, but we have to put limits to it. B/c eventually you run to of space. Two problems with recursion: subproblems that are similar or smaller and closer to a base case, a base case that can be solved without recursion. Example: int factorial( int n) { if (n == 0) { else { return 1; return n* factorial (n-1); Recursion and the stack: (from the example above) x = 6. 2 main factorial factorial factorial factorial int x = factorial (3); In recursive programs: computation is done after the repetition, multiplication happens during passive ow, we need to keep track of each stack frame with each value of n. In iterative programs: computation is done before the repetition , multiplication happens in active ow (there"s no stack frame holding these values, once a value of n is multiplied into result, we can just forget it.