[Python] 재귀 함수

  재귀 함수

• 재귀 : 자기 자신을 호출하는 것
• 재귀 함수를 사용하여 팩토리얼을 구할 수 있음

f(3) = 3 * f(2)
      = 3 * 2 * f(1) * f(0) -> f(0)은 1임
      = 3 * 2 * 1 * 1

# 재귀 함수로 팩토리얼을 구하기
def factorial(n):
    # n이 0이라면 1을 리턴
    if n == 0:
        return 1
    # n이 0이 아니라면 n * (n - 1)을 리턴
    else:
        return n * factorial(n-1)
    
print("1! : ", factorial(1) )
print("2! : ", factorial(2) )
print("3! : ", factorial(3) )
print("4! : ", factorial(4) )
print("5! : ", factorial(5) )

 

  재귀 함수의 문제

• 상황에 따라 기하급수적으로 많이 반복함
• 시간이 오래 걸리는 상황이 발생

 

  재귀 함수의 문제 해결

• 메모화 : 딕셔너리를 사용해서 한 번 계산한 값을 메모(저장)하여 반복 수행하지 않고 곧바로 값을 돌려 줌으로써 코드의 속도를 빠르게 함

dictionary = {
    1: 1,
    2: 1
}

# 피보나치 수열 : 첫째 둘째항이 1이며 그 뒤에 모든 항은 바로 앞 두 항의 합인 수열

def fibonacci(n):
    if n in dictionary:
        # 메모가 되어 있으면 메모된 값을 리턴
        return dictionary[n]
    else :
        # 메모가 되어 있지 않으면 값을 구함
        output = fibonacci(n - 1) + fibonacci(n - 2)
        dictionary[n] = output
        return output

print("fibonacci(10):", fibonacci(10))
print("fibonacci(20):", fibonacci(20))
print("fibonacci(30):", fibonacci(30))
print("fibonacci(40):", fibonacci(40))
print("fibonacci(50):", fibonacci(50))

• 조기 리턴 : 코드 중간에 return 키워드를 사용하는 것

def fibonacci(n):
    if n in dictionary:
        # 메모되어 있으면 메모된 값 리턴
        return dictionary[n]
        
    # 메모되어 있지 않으면 값을 구함
    output = fibonacci(n-1) + fibonacci(n - 2)
    dictionary[n] = output
    return output
    
    
print("fibonacci(10):", fibonacci(10))
print("fibonacci(20):", fibonacci(20))
print("fibonacci(30):", fibonacci(30))
print("fibonacci(40):", fibonacci(40))
print("fibonacci(50):", fibonacci(50))