# 19.11: Exercises

- Page ID
- 16969

Exercise \(\PageIndex{1}\)

*Draw a stack diagram for the following program. What does the program print?*

def b(z): prod = a(z, z) print z, prod return prod def a(x, y): x = x + 1 return x * y def c(x, y, z): total = x + y + z square = b(total)**2 return square x = 1 y = x + 1 print c(x, y+3, x+y)

**Solution:**

Exercise \(\PageIndex{2}\)

*The Ackermann function, A(m, n), is defined:*

*See http://en.Wikipedia.org/wiki/Ackermann_function. Write a function named *`ack`

* that evaluates Ackermann’s function. Use your function to evaluate *`ack(3, 4)`

*, which should be 125. What happens for larger values of *`m`

* and *`n`

*?*

**Solution:**

Exercise \(\PageIndex{3}\)

*A palindrome is a word that is spelled the same backward and forward, like “noon” and “redivider”. Recursively, a word is a palindrome if the first and last letters are the same and the middle is a palindrome.*

*The following are functions that take a string argument and return the first, last, and middle letters:*

def first(word): return word[0] def last(word): return word[-1] def middle(word): return word[1:-1]

*We’ll see how they work in Chapter 8.*

*Type these functions into a file named*`palindrome.py`

*and test them out. What happens if you call*`middle`

*with a string with two letters? One letter? What about the empty string, which is written*`''`

and contains no letters?*Write a function called*`is_palindrome`

that takes a string argument and returns`True`

*if it is a palindrome and*`False`

*otherwise. Remember that you can use the built-in function*`len`

*to check the length of a string.*

Exercise \(\PageIndex{4}\)

*A number, a, is a power of b if it is divisible by b and a/b is a power of b. Write a function called *

`is_power`

that takes parameters `a`

*and*

`b`

*and returns*

`True`

*if*

`a`

*is a power of*

`b`

*. Note: you will have to think about the base case.*

Exercise \(\PageIndex{5}\)

*The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.*

*One way to find the GCD of two numbers is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.*

*Write a function called gcd that takes parameters a and b and returns their greatest common divisor.*

* Credit: This exercise is based on an example from Abelson and Sussman’s *Structure and Interpretation of Computer Programs

*.*