# Exercise 6.4 Draw A Stack Diagram For The Following Program

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

prod = a(z, z) print z, prod return prod def a(x, y) : x = x + 1 return x * y def c(x, y, z)

sum = x + y + z pow = b(sum)**2 return pow x = 1 y = x + 1

Exercise 6.5 The Ackermann function, A(m,n), is defined3:

Write a function named ack that evaluates Ackerman's function. Use your function to evaluate ack (3, 4), which should be 125. What happens for larger values of m and n?

Exercise 6.6 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

def last(word):

return word[-1]

def middle(word):

return word[1:-1]

We'll see how they work in Chapter 8.

1. 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?

2. 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 6.7 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_powe r that takes parameters a and b and returns True if a is a power of b.

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

3See wikipedia.org/wiki/Ackermann_function

4This exercise is based on an example from Abelson and Sussman's Structure and Interpretation of Computer Programs.

One way to find the GCD of two numbers is Euclid's algorithm, which 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 consider gcd(a, 0) = a.

Write a function called gcd that takes parameters a and b and returns their greatest common divisor. If you need help, see wikipedia. org/wiki/Euclidean_algorithm.