Recursion using pass by reference

개요

What is it?

memory allocation

• call frame

recursion 에서의 주의점

• recursion시 변수 메모리

마무리

 

 

 

 

개요

여러 코딩테스트 문제를 풀다 보면, 재귀를 사용하는 경우가 많습니다. 재귀를 사용하여 로직을 짜게되면, 이전 call frame에서의 state가 보존이 안되는 경우가 저는 많았습니다. 이는 pass by reference에 대하여 명확히 인지하지 않고 로직을 작성해서 발생한 일입니다.

 

 

 

 

what is it

 

reference 를 변수에 assignment 하게 되면 , 메모리에 가리키게 된다고 표현합니다. 이는 변수를 box라 표현하는 C스러운 표현이라고 생각합니다. Fluent Python 이라는 책에서는 이는 sticker 를 붙인다고 표현합니다. 

Fluent Python, Chapter 8

함수에 parameter에 reference를 넘겨주게 된다면, 메모리가 할당된 object에 sticker를 붙이게 될 것입니다.

 

 

 

memory allocation

 

call frame 안에서의 local variable이 같은 object에 sticker를 붙이게 된다는 것은 무슨 의미일까요? 메모리에 어떻게 할당 되는지 알아야 변수를 내가 의도한 대로 수정 할 수 있습니다.

 

call frame

 

li=[1,2,3]
a=li

a[2] = 4

print(a is li)


print(a)
print(li)

위와 같은 단순한 코드에 대한 메모리 구조를 시각화 해보겠습니다.

2번째 line a= li 까지 수행 했을 때의 메모리 구조입니다. 

4번째 line 까지 수행했을 때 의 메모리 및 출력문입니다.

a,li 가 같은 object를 가리키기 때문에 li is a 는 True를 출력합니다. 

 

 

recursion에서의 주의점

사실 위 내용은 저도 기존에 알고 있었던 사실입니다. 하지만, 이를 본질을 못하고 그저 저 상황만을 외우고 있었기에 다른 상황에서의 적용이 안되었습니다. 제가 recursion에서 자주 저지르던 실수를 보여드리도록 하겠습니다.

 

 

recursion 시 변수 메모리

 

def fib(n,li):
    if n==1 or n==0:
        # li.append(n)
        return 1
    li.append(n-1)
    a= fib(n-1,li)
    li.append(n-2)
    b= fib(n-2,li)
    print(li)
    return a+b


li=[]
fib(4,li)

print(li)

.

단순한 fibnoach 수열을 구현한 코드입니다. li의 용도는 fibonachi의 몇번 째 항을 계산하였는지 출력해 주는 리스트입니다. li 는 call frame에서 지역 변수임으로 call frame의 호출이 종료되면 li는 사라지고 , 재귀를 호출한 call frame으로 돌아가게 되면, 호출한 frame에서의 li는 이전 state를 보존하고 있다고 저는 생각했었습니다. C 스타일의 call frame에 대한 사고 방식입니다. 이 사고방식은 변수를 box라고 생각하기 때문에 일어난 오해입니다. Pythonic 하지 못합니다.

n=2일 때 fib(1) + fib(0)를 계산하고 , 이전 state를 보관하고 있던 li를 출력할려고 합니다. 이전 state에서 담아두었던, 숫자는 1,0 이기 때문에 1,0만이 출력이 되어야합니다. 하지만, python의 variable을 sticker이기 때문에 global frame에서 생성 되었던 object li에 sticker를 붙이고 있습니다. 이전에 호출 되었던 call frame에서의 숫자 3,2, 가 list에 먼저 들어가 있게 되는 것입니다.

 

이 문제는 li = []라는 코드로 매 호출시 별개의 object인 li를 생성해주면 해결이 되는것입니다.  

예제가 부적절 하지만 , 하고 싶은 얘기는 parameter로 mutable reference를 넘겨주게 된다면 , parameter의 sticker를 같은내용을 담고있는 별개의 object에 붙여주어야 한다는 것입니다.  예를들어, list(), list comprehension  정도가 생각이 납니다. 

 

 

마무리

 

사실 별 내용은 아닌거 같지만, Deep Learning Research  Engineer ,를 넘어서 AI Research engineer를 희망하는 저는 neural net 뿐만 아니라 다양한  custom model을 작성하게 되는 경우가 종종 생길겁니다. Skip Connection이라는 method가 나온이후 , deep learning model의 layer 수는 100단위를 넘길 수 있습니다. 이 때 , 메모리 올리게 되는 parameter 수는 상상을 초월할 것입니다. 여기서, 메모리 관련 실수를 한다면 이를 일일이 debugging으로 해결 할 수 없습니다. AI 기술에 관한 지식도 중요하지만, 이를 뒷받침하는 Python,Mathmatics 등의 기초 실력이 없다면, 가진 능력을 다 발휘 못할 것입니다. 밸런스 있는 성장을 잘 하도록 공부의 균형을 맞출려고 노력해야합니다.