이번 포스팅에서는 Python의 재귀함수가 스택을 활용한다는 점과 Python에서의 지역변수, 전역변수를 살펴보려고 한다. 이번 내용은 생각보다 기초적인 개념이지만 알고리즘 공부를 하면서 몰랐던 내용 중심으로 포스팅하려고 한다.
1. 재귀함수는 스택을 활용한다!
재귀함수는 스택을 활용한다는 것을 알고리즘 공부하면서 솔직히 처음 알았다. DFS 관련 문제를 풀기 시작했는데, 재귀함수가 아직도 와닿지 않았었는데, 스택을 활용한다는 것을 듣고 '아!' 소리가 절로 나왔다. 이런 기초적인 내용을 이제야 알았다는 것에 아쉽긴 하지만 지금이라도 안 게 어딘가!
먼저 스택이란 자료구조는 처음 들어간 데이터가 가장 나중에 나오는 FILO(Frist In Last Out) 방식을 취하는 자료구조이다. 아래처럼 말이다.
그런데 재귀함수가 이런 스택의 방식인 FILO 방식대로 호출된다. 예를 들어서, 아래와 같은 함수가 있다고 가정해보자.
def dfs(x):
if x > 0:
print(x, end=' ')
dfs(x-1)
dfs(5)
print('>> 재귀함수 종료!')
위 소스코드를 출력해보면 아래처럼 5, 4, 3, 2, 1 순서로 출력된다는 것을 볼 수 있다. 위 재귀함수 소스코드는 머릿속으로 상상하기도 쉽다.
하지만 print() 출력문을 재귀함수 밑 라인으로 바꾸어서 출력하면 출력 결과가 반대로 출력되는 것을 볼 수 있다.
def dfs(x):
if x > 0:
dfs(x-1)
print(x, end=' ')
else:
print('이제 호출 시작! >> ', end=' ')
dfs(5)
print('>> 재귀함수 종료!')
물론 사람마다 다 다르겠지만 필자는 처음에 재귀함수가 스택 구조를 활용한다는 사실을 모른 채 위 소스코드 결과를 상상하려니 자꾸 머릿속이 얽혔다. 그래서 위 소스코드를 기준으로 재귀함수가 호출하는 순서를 도식화해서 그려보기로 하자.
함수를 호출하면 스택이라는 자료구조에 호출한 함수, 함수의 파라미터 값, 메모리 주소, 해당 함수가 끝나고 어디로 복귀해야하는지에 대한 여러가지 정보가 저장된다고 한다. 이렇게 하나의 함수에 대해 스택에 저장되는 정보들을 하나로 묶어 '스택 프레임'이라고도 한다.
그러면 호출될 재귀함수에 대한 정보가 아래처럼 스택 자료구조에 쌓인다.
맨 위 함수인 dfs(0) 함수는 dfs 함수 내에 if 조건문에 위배되기 때문에 print 문으로 빠져 함수가 종료된다. 그러면서부터 이제 스택에 쌓인 함수 하나하나씩 호출이 된다. 스택에 쌓이는 함수 정보에는 해당 함수가 호출이 끝나고 어디 함수로 가야하는지에 대한 정보를 담고 있어 적절히 다음에 호출할 함수를 찾아갈 수 있다.
계속 스택에서 pop 하면서 함수를 호출해준다.
이렇게 스택구조를 활용한다고 생각하니 재귀함수가 구현되는 과정을 이제야 좀 머릿속으로 그려질 수 있는 듯 하다!
2. Python의 지역변수와 전역변수
메인 스크립트 영역에서 할당되는 전역변수는 메인 스크립트에 존재하는 모든 함수가 공용으로 접근이 가능하다. 하지만 지역변수는 함수 내에서 새롭게 할당하는 변수를 의미한다. 그런데 이 두 변수가 이름이 같아지거나 하는 경우에 헷갈릴 수 있는 상황이 발생한다.
우선 아래와 같은 소스코드가 있다고 가정하자.
def func():
if cnt == 100:
print(cnt)
if __name__ == '__main__':
cnt = 100
func()
print(cnt)
현재 메인 스크립트에서 전역변수로서 cnt = 100으로 할당했다. 이 때, func() 이라는 함수 내부에서 if 조건문에도 변수 cnt가 사용되고 있다. 이 때, func() 함수안에서의 cnt는 전역변수로서의 cnt를 참조할 수 있다.
그런데, 만약 func() 함수 안을 아래와 같이 바꾸었다고 가정해보자.
def func():
if cnt == 100:
cnt = 777
print(cnt)
if __name__ == '__main__':
cnt = 100
func()
print(cnt)
func() 함수안에서 cnt 라는 변수를 777이라는 값으로 "새롭게 할당" 했다. 이렇게 새롭게 할당을 하는 등호(=)가 들어가게 되면 파이썬에서는 이를 지역변수로 해석을 하게 된다. 파이썬은 소스코드를 실행하기 전에 인터프리터가 코드를 모두 해석한 후에 순차적으로 실행하는 과정으로 이루어진다고 한다.
따라서 위와 같이 소스코드를 작성하게 되면 파이썬 인터프리터가 코드를 해석할 때, func() 함수 내부의 cnt = 777 이라는 코드를 보고 "아, cnt라는 새로운 지역변수를 생성했구나" 라고 해석한다. 그리고 해석이 모두 끝난 후 소스코드를 순차적으로 실행할 때, func() 함수 내부의 if cnt == 100 조건문을 보고난 후, "어, 해석할 때 cnt가 지역변수로 생성했다고 했는데, cnt라는 지역변수가 만들어지기 전에 어떻게 cnt == 100 이라는 조건문을 처리하지?" 라고 하면서 "UnboundLocalError: local variable 'cnt' referenced before assignment" 와 같은 에러를 발생시킨다.
이 때, 발생하는 에러를 해결하기 위해서 바로 global 이라는 것으로 cnt가 전역변수라는 것을 인터프리터에게 알려줄 수 있다. 그래서 다음과 같이 소스코드를 고치면 정상적으로 실행된다.
def func():
global cnt
if cnt == 100:
cnt = 777
print(cnt)
if __name__ == '__main__':
cnt = 100
func()
print(cnt)
그동안 global을 언제 사용하는 건지 정확히 몰랐는데, 이번 기회에 알게 되었다!
그런데 한 가지 또 알아볼 것이 있다. 바로 리스트에 있어서는 원소를 바꾸거나 append, pop할 때는 global 이라는 것을 선언해주지 않아도 된다. 아래 소스코드를 실행하면 정상적으로 실행이 된다.
def func():
cnt[0] = 777
cnt.append(555)
cnt.pop()
if __name__ == '__main__':
cnt = [1,2,3,4]
func()
print(cnt)
하지만 리스트도 func() 함수 내에서 새롭게 정의하게 될 때, global을 사용하지 않으면 지역변수로 여겨 또 "UnboundLocalError: local variable 'cnt' referenced before assignment" 에러를 발생시킨다. '새롭게 정의' 한다는 의미는 아래와 같다.
def func():
cnt += [555]
if __name__ == '__main__':
cnt = [1,2,3,4]
func()
print(cnt)
위처럼 리스트에 원소를 추가하는 방법으로 '+' 연산자를 사용할 수 있다. 하지만 이렇게 하면 등호('=')를 사용하기 때문에 지역변수로 인터프리터가 해석하게 된다. 그래서 인터프리터는 소스코드를 실행할 때, "어, cnt라는 지역변수 리스트에 555를 추가해야 하는데, cnt라는 지역변수가 아직 정의되지 않았는데 어떻게 추가하라는 말이야?" 하면서 에러를 내뱉게 된다.
따라서 위 에러를 해결하기 위해 global 을 사용한다.
def func():
global cnt
cnt += [555]
if __name__ == '__main__':
cnt = [1,2,3,4]
func()
print(cnt)지금까지 재귀함수가 스택 방식으로 호출된다는 점과 파이썬에서 지역변수, 전역변수를 처리하는 데 있어서 헷갈릴만한 점에 대해 알아보았다. 알고리즘 풀이에 자주 사용될 수도 있을 듯 하다!
'Python > 알고리즘 개념' 카테고리의 다른 글
| [Python] 가장 긴 증가하는 부분 수열 길이를 찾는 LIS 알고리즘 (0) | 2021.10.15 |
|---|---|
| [Python] 알아두면 좋을 기타 알고리즘 (0) | 2021.10.02 |
| [Python] 노드 간의 선후 관계를 고려하는 위상(Topology) 정렬 알고리즘 (0) | 2021.09.30 |
| [Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘 (5) | 2021.09.29 |
| [Python] 그래프 알고리즘 - 서로소 집합 자료구조 (5) | 2021.09.27 |
