Grokking Algorithms

CHAPTER 3
3.1
Suppose I show you a call stack like this.
What information can you give me, just based on this call stack? 
 Answer: 
Here are some things you could tell me:
• The 
greet
function is called first, with 
name = maggie.
• Then the 
greet
function calls the 
greet2
function, with
name = maggie
.
• At this point, the 
greet
function is in an incomplete,
suspended state.
• The current function call is the 
greet2
function.
• After this function call completes, the 
greet
function will 
resume.
3.2
Suppose you accidentally write a recursive function that runs 
forever. As you saw, your computer allocates memory on the
stack for each function call. What happens to the stack when
your recursive function runs forever?
 Answer: 
The stack grows forever. Each program has a limited 
amount of space on the call stack. When your program runs 
out of space (which it eventually will), it will exit with a stack-
overflow error.
answers to exercises

---

226
CHAPTER 4
4.1
Write out the code for the earlier 
sum
function.
 Answer:
def sum(list):
if list == []:
return 0
return list[0] + sum(list[1:])
4.2
Write a recursive function to count the number of items in a list.
 Answer:
def count(list):
if list == []:
return 0
return 1 + count(list[1:])
4.3
Find the maximum number in a list.
 Answer:
def max(list):
if len(list) == 2:
return list[0] if list[0] > list[1] else list[1]
sub_max = max(list[1:])