When could we get into an infinite loop with the fibonnaci code below? What data type do we require for the parameters? Add some additional conditions (guardians) to the code to prevent such issues.

```
def fibonacci (n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
```

Write a compare function that returns `1`

if `x > y`

, `0`

if `x == y`

, and `-1`

if `x < y`

.

Use incremental development to write a function called hypotenuse that returns the length of the hypotenuse of a right triangle given the lengths of the two legs as arguments. Record each stage of the development process as you go.

Write a function `is_between(x, y, z)`

that returns `True`

if $x ≤ y ≤ z$ or `False`

otherwise.

The Ackermann function, $A(m, n)$, is defined:
$$ A (m, n) = \left\{
\begin{array}{ll}
n + 1 & \mathrm{if}\ m = 0 \\
A (m - 1, 1) & \mathrm{if }\ m > 0 \mathrm{\ and\ } n = 0 \\
A (m - 1, A (m, n - 1)) & \mathrm{if}\ m > 0 \mathrm{\ and\ } n > 0
\end{array}
\right.
$$
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$?

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.

Show that `is_palindrome`

can be applied to lists as well.

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.

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.

```
In [3]:
```a = 1 < 0

```
In [4]:
```print a

```
```

```
In [ ]:
```