파이썬으로 배우는 자료구조 핵심 원리

파이썬으로 배우는 자료구조 핵심원리

스택프레임

1. 함수가 호출되면 메모리에는 스택 프레임이라는 공간이 생긴다. 여기에는 함수 실행에 필요한 지역 변수들이 할당된다.
2. 스택 프레임의 생성 시기는 함수를 호출했을 때고, 소멸 시기는 함수 실행이 종료되었을 떄이다.
3. 스택 프레임은 메모리에 생성되는데 생성될 수 있는 크기에 한계가 있다. 그러므로 계속 쌓인다면 언젠가는 최대 한계치에 도달할 수밖에 없다. 이 때 발생하는 에러가 Recursion Depth 에러이다.
4. 재귀 함수를 스택 프레임의 관점에서 바라보면 상태 정보를 가지고 있는 지역 변수는 서로 다른 스택프레임에 저장된다. 실행 결과는 서로 다른 스택 프레임에 있는 지역 변수에 저장된다. 이때 기저 사례를 두지 않으면 계속 호출이 일어나고 스택프레임이 저장되는 메모리가 한정적이기 때문에 언젠가는 오류가 발생한다.
5. 메모리 공간이 모자라게 되는 에러를 스택 오버 플로라고 한다.

재귀 함수

• 재귀 함수를 설계할 때는 두 가지를 고려해야 한다.
  1. 언제 어떤 인수를 전달하여 호출할 것인가
  2. 재귀 호출을 멈추는 조건인 기저 사례를 정하는 것