[자료구조] 스택(Stack)과 재귀 함수

스택은 블록 쌓기에 비유할 수 있다. 블록은 아래에서부터 위로 차곡차곡 쌓아가고, 아래에 있는 블록을 치우기 위해선 위에 있는 블록부터 먼저 치워야한다. 즉 선입후출, FILO구조이다.

스택 in 파이썬

파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요 없이 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()         # 가장 뒤쪽(위쪽) 원소 추출
stack.append(1)
stack.append(4)
stack.pop()

print(stack)        # 최하단 원소부터 출력
print(stack[::-1])  # 최상단 원소부터 출력

# [5, 2, 3, 1]
# [1, 3, 2, 5]

재귀 함수

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지 종료 조건을 꼭 명시해야 한다. 자칫 종료조건을 명시하지 않으면 함수가 무한 호출될 수 있기 때문이다.

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예이다.

재귀 함수의 형태를 알아보기 위해 대표적 예시인 팩토리얼 예제를 보자

재귀 함수 예제

우선 iter 반복으로 구현한 팩토리얼 예제 코드이다.

def factorial_iterative(n):
  result = 1
  for i in range(1, n + 1):
    result *= i
  return result

다음은 재귀 함수로 구현한 팩토리얼 예제 코드이다.

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

위 두 코드의 실행결과는 동일하지만 재귀 함수를 사용했을 때의 코드가 더 간결하다는 것을 알 수 있다.

이는 재귀 함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문이다. 점화식이란 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.

References

이것이 코딩 테스트다 with 파이썬