Algorithm - 재귀함수와 스택 자료구조(선수지식)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

선수지식(algorithm)

간단한 예제를 통해 재귀함수와 스택 자료구조의 원리를 이해하고자 한다.

 

 

---

 

예제(Python)

답안

import sys
sys.stdin = open('AA/input_preknowledge.txt', 'rt')

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

if __name__ == "__main__":
    n = int(input())
    DFS(n)
    
# 출력 : 1 2 3

 

input_preknowledge.txt(입력)

3

 

 

중요내용

1. 재귀함수는 자기자신을 호출하는 함수이다.
2. 재귀함수가 작동하는 과정에서 스택 자료구조가 사용된다.
3. 알고리즘 문제 풀이에서 재귀함수는 주로 반복문의 대체재로 사용된다.
4. 위의 예제에서 if __name__ == "__main__" 안의 코드가 메인 코드이며, 해당 if절 밖의 코드가 재귀함수를 정의하는 코드이다.

 

 

참고내용(재귀함수 & 스택 자료구조 원리)

1. 위의 예제에서 재귀함수의 매커니즘은 다음과 같다.
2. 변수 n에 3이 입력되면, 해당 입력 값은 if절의 DFS(n) 함수에 인자로 들어간다. (즉, DFS(3)이 됨)
3. DFS(3)이 호출되면 DFS() 함수의 정의대로 x가 0보다 클 때, DFS(x)에 들어온 인자(x)가 DFS(x-1)에 인자로 들어간다.
4. 즉, DFS(x-1)에 들어간 3은 다시 DFS(2)를 호출하고 DFS() 함수의 정의에 따라 x가 0보다 클 때 다시 DFS(1)를 호출한다.
5. 이러한 과정을 반복하면 DFS(0)까지 호출되고, 이 경우에는 if절의 조건을 충족시키지 못하므로(x = 0), 재귀함수는 중지된다.
6. 위의 과정이 반복되는 동안 스택 자료구조에는 DFS(3), DFS(2), DFS(1), DFS(0)의 데이터가 순서대로 쌓이게 된다.
7. DFS(n)의 데이터가 쌓일 때, 스택 자료구조에는 매개변수 x 값과 복귀주소가 포함된 스택 프레임이 만들어진다. (단, 지역변수가 존재하는 경우에는 스택 프레임 안에 지역변수도 함께 포함됨)
8. 여기서 매개변수 x는 DFS() 함수의 인자로 들어온 값을 의미하며, 복귀주소는 해당 함수인 DFS()가 종료되면 복귀하게 되는 위치를 의미한다.
9. 복귀주소는 DFS(x) 함수가 호출되기 직전의 위치로 기록된다.
10. 예를 들면, DFS(3) 함수의 매개변수는 x = 3이고, 복귀주소는 if __name__ == "__main__" 안의 DFS(n) 코드가 작성된 위치이다.
11. 다시 DFS(0)이 호출되는 시점으로 돌아가면, DFS(0)의 매개변수는 0이므로 if절의 조건이 충족되지 않아 재귀함수는 종료된다.
12. 이렇게 재귀함수가 종료되는 시점에서 스태 자료구조에 쌓여있는 DFS(0)의 데이터는 삭제되고 파이썬은 DFS(0)의 복귀주소인 DFS(1) 코드가 위치한 곳으로 이동하여 그 다음 코드를 실행시킨다.
13. 그 결과 DFS(1)의 다음 코드는 print(x, end=' ')이므로, x 값인 1이 출력되는 것이다. (DFS(1)의 매개변수가 1이기 때문)
14. 1을 출력한 후에 재귀함수가 종료되면, 동일한 원리로 스택 자료구조의 DFS(1) 관련 데이터는 삭제되며 파이썬은 DFS(1)의 복귀위치로 이동하여 DFS(2)의 다음 코드인 print문을 실행시킨다. (print문으로 2가 출력되는 이유)
15. 위의 과정을 반복하여 결국 1, 2, 3이 출력되고, 스택 자료구조에 쌓여있는 모든 데이터가 제거되어 재귀함수도 함께 종료된다.