# Python入门练习 - 递归

本文最后更新于：2020年10月23日 上午

## Problem 1. Exponent by iteration

Write an iterative function ** iterPower(base, exp)** that calculates the exponential

**by simply using successive multiplication. For example,**

*base*^{exp}**should compute**

*iterPower(base, exp)***by multiplying**

*base*^{exp}**times itself**

*base***times. Write such a function below.**

*exp*This function should take in two values - ** base** can be a float or an integer;

**will be an integer ≥ 0. It should return one numerical value. Your code must be iterative - use of the ** operator is not allowed.**

*exp*## Answer 1

```
def iterPower(base, exp):
result = 1
while exp > 0:
result *= base
exp -= 1
return result
```

## Problem 2. Exponent by recurse

In Problem 1, we computed an exponential by iteratively executing successive multiplications. We can use the same idea, but in a recursive function.

Write a function ** recurPower(base, exp)** which computes

**by recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by**

*base*^{exp}**to solve the initial problem.**

*base*This function should take in two values - ** base** can be a float or an integer;

**will be an integer ≥0. It should return one numerical value. Your code must be recursive - use of the ** operator or looping constructs is not allowed.**

*exp*## Answer 2

```
def recurPower(base, exp):
result = 1
if exp == 0:
return result
return base*recurPower(base, exp-1)
```

## Problem 3. The greatest common divisor(1)

The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder.

For example:

```
gcd( 2, 12) = 2
gcd( 6, 12) = 6
gcd( 9, 12) = 3
gcd(17, 12) = 1
```

Write an iterative function, ** gcdIter(a, b)**, that implements this idea. One easy way to do this is to begin with a test value equal to the smaller of the two input arguments, and iteratively reduce this test value by 1 until you either reach a case where the test divides both

**and**

*a***without remainder, or you reach 1.**

*b*## Answer 3

```
def recurPowerNew(base, exp):
if exp <= 0:
return 1
elif exp % 2 == 0:
return recurPowerNew(base*base, exp/2)
return base * recurPowerNew(base, exp - 1)
```

## Problem 4. The greatest common divisor(2)

The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder.

For example:

```
gcd( 2, 12) = 2
gcd( 6, 12) = 6
gcd( 9, 12) = 3
gcd(17, 12) = 1
```

A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that ** a** and

**are two positive integers:**

*b*- If
, then the answer is*b = 0**a* - Otherwise,
is the same as*gcd(a, b)**gcd(b, a % b)*

Write a function ** gcdRecur(a, b)** that implements this idea recursively. This function takes in two positive integers and returns one integer.

## Answer 4

```
def gcdIter(a,b):
result = min(a,b)
while a % result != 0 or b % result != 0:
result -= 1
return result
```

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！