[Python] Recursion 재귀 함수

Recursive function(재귀 함수): A function that the body calls the function itself (either directly or indirectly)

즉, 자기 자신을 호출하는 함수입니다.

 

재귀 함수는 두가지 요소로 구성되는데, 구성은 항상 base case와 recursive case로 구성되어 있습니다.

 

base case: 재귀 호출을 멈추기 위한 종료 조건입니다. 재귀 함수에선 이 base case를 정의하지 않으면 함수가 영원히 끝나지 않기에 탈출 조건으로도 여겨집니다 (사실상 앞이랑 같은 말ㅎㅎ)

recursive case: 재귀되는 부분인데, 문제의 크기를 점점 줄여가는 방식으로 이루어집니다. 밑에 예시중 swipe문제에서 확실히 보게 되겠지만, 재귀 호출이 종료 조건을 만족하게 되면, 호출된 순서의 반대 순서로 즉, 재귀 호출이 역순으로 반환됩니다.

 

Mutual recursion: Mutual recursion is when the function calls another function, and that other function calls the original function. A와 B라는 함수가 각각 정의되어 있다고 해봅시다. 이때, A함수는 B함수를 호출하는 함수이고, B함수는 반대로 A함수를 호출하는 함수라고 해볼게요. 이렇게, 서로 다른 함수가 서로를 호출하는 경우를 상호 재귀(mutual recursion)이라고 표현합니다. 예시 7번 문제에서 해당 개념을 살펴볼겁니다.

 

Tree recursion: Whenever executing the body of a recursive function, it makes more than one call to that function.

하나의 함수가 자기 자신을 여러번 호출하는 걸, tree recursion이라고 표현합니다. 한 함수 호출이 여러 개의 하위 호출을 낳는 구조가 트리 재귀라고 할 수 있겠습니다. 예시 8번에서 다뤄보겠습니다~

 

---

Practice 1 Factorial

def factorial(n):
    if n == 0:
        return 1
    return factorial(n-1) * n

 

base case: n = 0인 경우, 0! = 1

recursive case: n > 0인 경우, (n-1)! * n

 

Practice 2 Fibonacci numbers 

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n-2) + fib(n-1)

base case: 1번항과 2번항은 값이 1이기 때문에, 리턴값을 1로 지정

recursive case: 3번째 항부터 적용 가능. n번째 항의 피보나치수열은 n-1번째와 n-2번째 항의 덧셈으로 정의된다.

 

Practice 3 Swipe (Discussion3 Quesitons)

Implement swipe, which prints the digits of argument n, one per line, first backward then forward. The left-most digit is printed only once. Do not use while or for or str. (Use recursion)

def swipe(n):
    if n < 10:
        print(n)
    else:
        print(n % 10)
        swipe(n // 10)
        print(n % 10)

 

Practice 4 Skip Factorial (Discussion3 Quesitons)

Define the base case for the skip_factorial function, which returns the product of every other positive integer, starting with n. It goes like: n * (n - 2) * (n - 4) * ...

def skip_factorial(n):
    if n == 1 or n == 2:
        return n
    else: 
        return n * skip_factorial(n - 2)

 

Practice 5 Is Prime (Discussion3 Quesitons)

Implement is_prime that takes an integer n greater than 1. It returns True if n is a prime number and False otherwise. Try following the approach below, but implement it recursively without using a while (or for) statement.

You will need to define another "helper" function (a function that exists just to help implement this one)

def is_prime(n):
    assert n > 1
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i = i + 1
    return True

 

Recursive function으로 변경하기:

def is_prime(n):
    def check_all(i):
        if n == i:
            return True
        elif n % i == 0:
            return False
        return check_all(i + 1)
    return check_all(2)

 

Practice 6  Recursive Hailstone (Discussion3 Quesitons)

First, pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Complete this recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

def hailstone(n):
    print(n)
    if n % 2 == 0:
        return even(n)
    else:
        return odd(n)
    
def even(n):
    return 1 + hailstone(n // 2)
    
def odd(n):
    if n == 1:
        return 1
    else:
        return 1 + hailstone(n * 3 + 1)

 

Practice 7 Mutually Recursive Functions (Tree Recursion Slide Questions)

Two functions f and g are mutually recursive if f calls g and g calls f.

def smallest_factor(n):
    "The smallest divisor of n above 1"
    
def unique_prime_factors(n):
    """return the number of unique prime factors of n
    >>> unique_prime_factors(51) # 3 * 17
    2
    >>> unique_prime_factors(9) # 3 * 3
    1
    >>> unique_prime_factors(576) # 2 * 2 * 2 * 2 * 2 * 2 * 3 * 3
    2
    """
    k = smallest_factor(n)
    def no_k(n):
        "Return the number of unique prime factors of n other than k"
        if n == 1:
            return 0
        elif n % k != 0:
            return
        else:
            return 
    return

 

함수를 완성하면:

def smallest_factor(n):
    "The smallest divisor of n above 1"
    
def unique_prime_factors(n):
    """return the number of unique prime factors of n
    >>> unique_prime_factors(51) # 3 * 17
    2
    >>> unique_prime_factors(9) # 3 * 3
    1
    >>> unique_prime_factors(576) # 2 * 2 * 2 * 2 * 2 * 2 * 3 * 3
    2
    """
    k = smallest_factor(n)
    def no_k(n):
        "Return the number of unique prime factors of n other than k"
        if n == 1:
            return 0
        elif n % k != 0:
            return unique_prime_factors(n)
        else:
            return no_k(n // k)
    return 1 + no_k(n)

 

Practice 8 Counting Partitions 

 

def count_partitions(n, m):
    if n == 0:
        return 1 
    elif n < 0:
        return 0 
    elif m == 0:
        return 0
    else:
        with_m = count_partitions(n-m, m)
        without_m = count_partitions(n, m-1)
        return with_m + without_m

---

환웅, Minor in Data Science & B.A. in Statistics at University of California, Berkeley