파이썬 스터디 36 - 재귀 함수

재귀 함수

재귀(recursion)란, '자기 자신을 호출하는 것'을 의미

재귀 함수의 예시 → 팩토리얼 계산

n! = n * (n - 1) * (n - 2) * ... * 1

n을 하나씩 줄여가며 곱하는 계산...재귀 함수를 통해 이를 아래와 같이 바꿀 수 있다.
n = 3 이라고 하면,

factorial(4) = 4 * factorial(3)
	     = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1

이를 코드로 나타내면 다음과 같다.

ex)

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

    
number = 4
result = factorial(number)
print("{}! = {}".format(number, result))

출력결과

 

재귀 함수 예제
ex)

def list_sum(num):
    if len(num) == 0:
        return 0
    else:
        return num[0] + list_sum(num[1:])

    
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result = list_sum(numbers)
print("리스트 요소들의 합은 {}".format(result))

출력결과

 

 

재귀 함수의 단점

같은 코드를 계속 반복 → 프로그램 속도 저하 MAX...

Why?
한 번 구한 값이어도 다음 계산을 하려면 처음부터 해당 지점까지 전부 다시 하는 것을 반복

해결법...메모이제이션(Memoization) 사용

ex)

메모이제이션 사용X 피보나치 함수

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

    
number = 10
result = fibonacci(number)
print("fibonacci{} = {}".format(number, result))

출력결과

메모이제이션 사용O 피보나치 함수

memo = {
    1: 1,
    2: 1
    }

def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    else:
        output = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
        memo[n] = output
        return output

    
number = 10
result = fibonacci_memo(number)
print("fibonacci_memo{} = {}".format(number, result))

출력결과

맨 위 memo 딕셔너리의 역할
 : 재귀 함수가 n = 1 또는 n = 2에 도달했을 때 더 이상 계산하지 않고 저장된 값을 반환
  (첫 번째 피보나치 수는 1, 두 번째 피보나치 수도 1)