Python入门练习 - 递归

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

Problem 1. Exponent by iteration

Write an iterative function iterPower(base, exp) that calculates the exponential baseexp by simply using successive multiplication. For example, iterPower(base, exp) should compute baseexp by multiplying base times itself exp times. Write such a function below.

This function should take in two values - base can be a float or an integer; exp will be an integer ≥ 0. It should return one numerical value. Your code must be iterative - use of the ** operator is not allowed.

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 baseexp by recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by base to solve the initial problem.

This function should take in two values - base can be a float or an integer; exp 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.

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 a and b without remainder, or you reach 1.

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 b are two positive integers:

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 协议 ,转载请注明出处!