[Python] 기본12. 재귀함수와 메모화

재귀함수의 예를 말하라면 팩토리얼과 피보나치 수열이 빠지지 않는다.

'재귀(recursion)'란 자기 자신을 호출하는 것이며,
함수를 선언할 때, 함수 안에 자기 자신을 호출하여 끊임없이 나를 불러내는 형태를 만들어낸다.

재귀함수

#재귀함수의 예

def factorial(n):
	if n == 0 :
    	return 1
    else: 
    	return n*factorial(n-1) #팩토리얼을 구현한 함수 내에 팩토리얼 함수를 사용했다.

위에서 팩토리얼을 계산하는 함수를 만들었다.
위 예시와 같이 factorial( )함수 안에서 다시 factorial( )함수를 호출하는 것을 볼 수 있다.
재귀함수를 사용하면 코드가 깔끔해져서 가독성이 좋다는 장점이 있다.

재귀함수의 문제점은 나를 계속 호출하면서 계산 해야 하는 양이 기하급수적으로 늘어나는 것이다.
이와 비슷한 재귀함수로 fibonacci( )함수를 구현했다고 가정하고 fibonacci(50)를 구하면, 계산 횟수는 1.8천만번이나 되고 계산하는데 걸리는 시간도 1시간이 넘게 걸린다.

저런식으로 구현하면 계산했던 값도 계속해서 또 계산하는 문제가 발생한다.
이런 비효율적인 계산 방식을 개선할 방법은 존재한다. 그건 바로 딕셔너리를 사용하는 것!
한 번 계산한 값을 딕셔너리에 저장하는 것을 파이썬에선 메모화(memoization)이라고 부른다.

메모화(memoization)

dictionary = {
    1:1,
    2:1
}

def fibonacci(n) :
    if n in dictionary:
        return dictionary[n]
    else:
        output = fibonacci(n-1) + fibonacci(n-2)
        dictionary[n] = output
        print("add output value = ", output) #추가하는 output 값을 보여줌
        print("dictionary status = ", dictionary) #추가하고 나서 dictionary 값을 보여줌
        return output
    
print("fibonacci(5)=", fibonacci(5))

'''
출력결과 :
add output value =  2
dictionary status =  {1: 1, 2: 1, 3: 2}
add output value =  3
dictionary status =  {1: 1, 2: 1, 3: 2, 4: 3}
add output value =  5
dictionary status =  {1: 1, 2: 1, 3: 2, 4: 3, 5: 5}
'''

위에서 재귀함수로 만든 함수로 fibonacci(50)을 계산하면 1시간이 넘게 걸린다고 했다.
위 코드와 같이 계산했던 값을 dictionary에 저장하고 딕셔너리에서 꺼내 쓴다면 코드의 속도가 굉장히 빨라진다.

else문 중간에 output과 dictionary를 프린트한 코드는 내가 코드 이해하려고 임의로 넣어놓았다.
메모화는 재귀함수랑 함께 많이 사용하는 기법이라고 하니 나중에 다시 보러 와야겠다.

조기리턴

위 피보나치수열을 구현한 함수 코드를 좀 더 가독성이 좋게 작성이 가능하다.

def fibonacci(n) :
    if n in dictionary:
        return dictionary[n]

    output = fibonacci(n-1) + fibonacci(n-2)
    dictionary[n] = output
    return output

중간에 return 키워드를 사용하는 것을 조기 리턴(early returns)이라고 부른다.
조기 리턴을 사용하면 들여쓰기 단계가 줄기 때문에 코드 가독성이 더 좋아진다.

* 추가로 피보나치 함수를 제대로 이해하지 못했다면 밑에 있는 return ouput에 대한 의문이 생길 것이다. 중간에 재귀함수로 호출한 fibonacci( )함수가 있기 때문에 계속해서 fibonacci( )함수를 호출하게 되므로 fibonacci(0)까지 도달해야 ouput으로 리턴을 시작한다.
함수 속으로 계속 깊숙히 들어가다 끝에 도달했을 때 다시 output리턴, output리턴, output리턴...하는 형태..인데 이건 말로 표현하기 힘들다. 함수 중간에 print( )함수 넣어서 함수 구조 확인해보는게 제일 빠를듯.