파이썬에서의 Stack 자료구조 활용 - 2

컴퓨터에서 메서드를 호출하는 순간, 해당 메서드는 메모리의 스택 프레임에 올라가게 되며 연속적으로 호출하면 쌓이게 된다.

 

이를 활용해서, 앞에서 소개한 스택 라이브러리를 사용하지 않고 재귀함수를 써서 특정 알고리즘을 구현할 수 도 있다.

 

예시

def recursive_function(i):
    if(i == 100):
        return
    print(i, '번째 재귀함수에서', i+1, '번째 함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수 종료')

recursive_function(1)

실행 결과

1번째 재귀함수에서 2번째 재귀함수를 호출합니다.
2번째 재귀함수에서 3번째 재귀함수를 호출합니다.
....
99번째 재귀함수에서 100번째 재귀함수를 호출합니다.
99번째 재귀함수 종료
98번째 재귀함수 종료
....
1번째 재귀함수 종료

 

위 결과를 보면, 100개의 스택이 쌓이는 순간 return문으로 빠져서 가장 상단의 stack부터 제거되는 것을 알 수 있다.

 

또 다른 예시로,  팩토리얼 값을 구하는 알고리즘을 구현하는 데에도 재귀함수를 활용할 수 있다.

 

n! 값 구하기

factorial_value = input()

def factorial_recursive(n):
     if(n <= 1)
         return 1
     return n * factorial_recursive(n - 1)

factorial_recursive(factorial_value)

 

재귀함수는 알고리즘 문제중, DFS(Deapth-First-Search, 깊이우선탐색) 및 BFS(Breadth-First-Search, 너비우선탐색)을 해결하는데 자주 쓰인다.