스택을 통해 재귀함수의 작동 과정에 대해 알아보자.

 

🙂 목적

재귀 함수를 접해보긴 했지만 개념을 두루뭉실하게 알고 있었고, 이로 인해 재귀 함수를 사용하여 해결해야 하는 알고리즘 문제들을 만났을 때 재귀와 관련된 코드 한 줄도 적지 못하고, 심지어 다른 사람의 재귀를 이용한 코드도 해석하지 못하는 불상사가 일어나게 되어 블로그에 재귀와 관련된 개념들을 정리해 보려고 한다.

예시 코드 자체는 매우 간단하지만 재귀함수와 스택을 관련지어 개념을 이해하는 것은 꽤 어려웠다.

위의 원리를 정확히 알고 있는 것이 완전탐색, DFS 등의 유형의 문제를 해결할 때 걸림돌이 되지 않으리라 생각한다.

 

❓ 재귀함수 (recursion)

재귀함수는 함수가 자기 자신을 반복하여 호출하는 함수를 말한다.

 

알고리즘 문제를 풀다 보면 다중 for문과 같이 반복문으로 작성하면 유연성이 떨어지게 되는 경우를 종종 볼 수 있다.  이때 재귀함수를 사용하여 코드를 작성하면 가독성이 높아지는 효과가 있다.

 

즉, 재귀함수는 반복문의 대체제로 사용 가능하다.

 

아래에서 매우 간단한 재귀함수의 예를 살펴보자.

 

< 재귀함수 예시 1️⃣ >

 

def DFS1(x):
    if x > 0:
        print(x, end=' ')
        DFS1(x - 1)

def main():
    n = int(input())
    DFS1(n)     # DFS는 깊이 우선 탐색의 의미
    
main()

# 터미널에 3을 입력한다.

 

main 함수는 사용자로부터 입력받은 값을 int형으로 만들어 변수 n에 할당한다.

변수 n은 DFS1의 인자로 들어가게 된다.

DFS1에서는 인자(x)로 들어온 숫자가 0보다 클 때만 그 숫자를 출력하고,  자기 자신인 DFS1의 인자로 현재 x에서 1을 뺀 값을 보내준다. 

x가 1씩 감소해 0이 되면 조건문이 False가 되므로 함수가 종료되게 된다.

 

* return문을 적어주지 않으면 None값으로 return을 호출하고 함수가 종료된다. 즉, None은 함수가 실행을 완료했으며 아무것도 반환하지 않음을 의미한다. 이를 '암시적 반환 유형' 이라고 한다.

따라서 return을 적어주지 않았다고 프로그램이 무한히 계속 실행되는 것이 아니다.

(반대로 return과 반환될 값을 적어준 경우 '명시적 반환 유형'이라고 함.)

 

위와 같은 예시의 경우 그냥 흐름을 따라 가면 되므로 답을 쉽게 예측 가능하다.

 

< 1️⃣ 답 >

 

3 2 1

 

 

 

❓ 재귀함수와 스택

재귀함수는 자료구조 중 후입선출 구조인 '스택' 을 사용하여 작동한다.

작동 방식은 아래 예제를 통해 살펴보자.

 

< 재귀함수 예시 2️⃣ >

 

def DFS2(x):
    if x > 0:
        DFS2(x - 1)
        print(x, end=' ')

def main():
    n = int(input())
    DFS2(n)     

main()

# 터미널에 3을 입력한다.

 

예시 1에서와 달라진 점은 DFS2가 자기 자신을 호출하는 코드가 먼저고, x값을 출력하는 코드가 그 이후라는 것이다.

 

우선 위 코드의 결과부터 살펴보면 다음과 같다.

 

1 2 3

 

이전 예시와 결과가 완전히 반대로 나왔다.

어떤 원리로 이러한 결과가 나오는지를 알려면 스택에 어떻게 데이터가 쌓이고 사라지는지 과정을 살펴보아야 한다.

 

main함수가 실행되는 맨 처음에, 사용자의 입력으로 3을 받았고 이를 int로 변환하여  변수 n에 할당해 주었다. 그리고 DFS2의 인자로 n(3)을 넣어주었다.

그러면 DFS2 함수가 호출된 것이므로 DFS2 함수에 대한 스택에는 다음과 같이 정보가 쌓이게 된다.

 

 

그림에서는 글로 풀어서 적었지만 실제로는 현재 함수의 매개변수의 주소에 인자로 들어온 숫자를 할당한 정보와, 이후에 복귀할 위치(주소)를 담은 정보가 스택에 쌓인다.

이 예제에서는 존재하지 않지만 지역변수가 존재하는 경우 그 주소와 할당된 값에 대한 정보도 들어간다.

그 밖에도 많은 정보들이 스택에 기록되지만 우리가 주의 깊게 봐야 하는 것은 위에 언급한 정보들이다.

 

위와 같이 스택에 있는 하나의 함수의 정보를 담은 한 덩어리는 '스택 프레임' 이라고 부른다. 

 

스택에 쌓여 있는 상태로 있으면 그 함수는 종료되지 않은 함수라는 뜻이다.

따라서 DFS2(3)는 작동중에 있는 함수가 된다.

 

스택에 기록했으니 DFS2(3)를 계속 실행해 보자.

3은 0보다 크므로 조건이 True가 되고, DFS2(x - 1)이 실행되게 된다. 

x에 3이 대입되어 DFS2(2) 함수가 호출되게 된다. x = 3에 이어서 자기 자신이 다시 호출된 것이다.

DFS2가 호출된 것이므로 아까와 같은 원리로 스택에 DFS2(2)에 대한 정보가 쌓이게 된다.

 

아직 DFS2(3)에서 DFS2 함수의 마지막 코드인 print문까지 실행한 것이 아니므로 DFS2(3)은 종료되면 안 된다. DFS(2)에 대한 정보가 그 위에 그대로 쌓이는 형태가 되어야 한다.

 

DFS2(2)에서는 복귀 지점이 main 함수가 아닌 DFS2(x-1)이 적혀 있는 부분이 된다.

DFS2(2)는 DFS2(3)의 실행 중에 나온 함수이므로 추후에 DFS2(3)의 실행을 이어나가기 위해서이다.

 

* DFS2(3)에서의 x와 DFS2(2)에서의 x는 서로 다른 x이다. 서로 다른 메모리 주소에 값이 할당되어 있다는 의미이다. 앞으로 스택에 쌓이는 x가 계속 나올 텐데,  그 모든 x들은 서로 다른 x들이라는 것을 명심해야 한다.

 

DFS2 함수의 조건으로 x가 0보다 클 때만 이라고 적혀 있으므로 위와 같은 과정을 DFS2(0)이 될 때까지 반복하면 된다. 그림으로 나타내면 다음과 같다.

 

DFS2(0)이 호출되어 스택에 쌓인 후 함수의 코드를 실행하려고 보니까 x > 0의 조건에서 False가 되게 된다.

이에 따라 DFS2(0)은 종료되게 되고, 적혀 있는 복귀 주소로 이동하게 된다. 

결과적으로 DFS2(1)의 DFS(x-1) 부분으로 이동하게 되고, DFS2(0)은 스택에서 완전히 빠지게 된다.

 

이제 DFS2(1)은 이전에 하던 작업을 마저 이어서 하게 된다. DFS2(x-1) 바로 아래의 코드인 print문을 수행하게 되고, 현재 매개변수 x에 할당된 숫자인 1이 출력되게 된다.

DFS2(1)에서는 DFS2 함수의 모든 작업을 마쳤으므로 이제 DFS2(1)은 종료되게 된다. 

아까와 마찬가지로 스택에 저장되어 있는 대로 DFS2(2)의 DFS2(x-1) 부분으로 복귀하고 DFS2(1)은 스택에서 사라지게 된다.

 

이 과정을 스택 안에 있는 모든 스택 프레임들이 사라질 때까지 반복한다.

 

마지막 DFS2(3)에 도달하면 3이 출력되고, main 함수의 DFS2(n)이 적혀 있는 위치로 복귀 후 DFS2(3)는 스택에서 빠지게 된다. 이로써 DFS2 함수는 완전히 종료되게 된다.

main 함수에서 DFS2(n) 이후로 수행할 코드가 없으므로 main 함수 또한 종료되게 된다.

 

이렇게 터미널에 1 2 3 이 출력된 모습을 볼 수 있게 된다.

 

 

 

📌 참고한 강의

파이썬 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의