[DS] Recursion(재귀 호출) 과 함수 호출 과정

# 재귀 호출의 개념

- 재귀 호출: 함수가 실행 중에 자기 자신을 다시 호출하는 상황

- 종료 조건을 가지는 동일한 task가 반복될 때 가능 // 종료 조건: 함수가 끝나야하기 때문에 필요

> 종결 조건은 재귀 호출에 반드시 포함되어야하며

잘못 설정할 경우 프로그램이 무한 반복에 빠질 수 있음

- 시스템 입장에서는 새로운 함수가 불리는 것과 같음

- 함수 실행 중 또 다른 함수가 실행되면 함수의 컨텍스트(context), 정보(지역변수, 복귀주소)를 활성 레코드(activation record)에 저장하여 보관하여야 함

- 활성 레코드는 함수의 환경 정보를 담고 있는 구조체이며 실행되는 함수마다 1개씩 생성되어 시스템 스택에서 저장 관리됨

- 시스템 스택은 함수 호출을 관리하기 위해 프로그램에서 사용하는 스택을 말하며 활성 레코드가 저장됨

 

 

# 활성 레코드

- 실행 중이던 함수의 context 정보를 활성레코드에 저장

* context: 지역 변수, 다시 시작해야하는 명령어의 주소, 이전 stack frame의 포인터

- 스택 프레임으로 함수마다 1개씩 생성됨

- procedure가 한 번 수행 될 때 필요한 정보들을 기억하는 장소의 연속 블록

* procedure: 컴퓨터 프로그래밍에서 목적에 사용되는 일련의 명령문들을 모아둔 것

- 새로운 함수가 호출될 때 해당 함수의 정보를 가지고 데이터의 형태로 묶여 스택에 저장됨

 

 

# 시스템 스택

[구조] 나중에 호출된 함수가 먼저 나와 실행하고 끝나는 구조로 LIFO

[호출]

- 함수나 프로그램이 호출되면 호출한 함수의 수행에 필요한 지역 변수와 매개 변수 그리고 수행 후 복귀할 주소들의 정보를 스택 프레임에 저장하며, 시스템 스택에 push하여 삽입

- 시스템 스택의 최상위 top은 항상 현재 실행 중인 함수이며, 스택 프레임임

[복귀]

- 함수의 실행이 끝나면 시스템 스택의 최상위 스택 프레임을 pop하여 삭제하면서 프레임에 저장된 주소를 확인하고 종료하게 됨

- 함수는 호출과 종료에 따라 반복되며, 수행 종료 시 시스템 스택은 공백 스택이 됨

[실행순서]

- 프로그램이 실행을 하며 메인 함수가 실행됨. 동시에 메인 함수와 관련된 정보를 스택 프레임에 저장하며 시스템 스택에 삽입하게 됨

- 메인 함수가 실행되면서 별도로 구현된 함수들이 실행됨. 함수를 담게된다면 호출과 복귀 정보를 스택 프레임에 담아 시스템 스택에 담게 되며 메인 함수로 복귀하기 위한 주소 값이 스택 프레임에 저장됨

- 불러들인 별도의 함수가 실행되며, 복귀할 때는 pop하여 스택 프레임에 있는 정보를 알게 됨

- 마지막에는 메인 함수가 남게되지만, 메인 함수는 복귀할 주소가 없으므로 프로그램이 종료되며 시스템 스택은 공백 스택으로 남게 됨

 

 

# 함수 호출 과정

1. 함수가 사용할 인자 값들을 스택에 넣고 함수의 시작 지점으로 점프해서 함수를 시작하면

해당 함수의 스택 프레임이 할당됨

2. 함수 내에서 사용할 스택 프레임 값들을 할당

3. 함수 내용을 수행

4. 함수가 끝나면 함수가 호출된 지점으로 복귀하기 위해 스택을 pop함

5. 호출한 지점의 다음 라인으로 점프하여 프로그램이 계속 실행됨

- 함수 호출 규약: 함수가 끝나고 복귀할 때 스택을 정리하는 여러가지 방법

A()                          // SS = [A]
{
  B()                        // SS = [A, B]
  {
    C(){                     // SS = [A, B, C]
        ...
        }                    // SS = [A, B] → C() 함수 호출이 끝나서 pop
    D(){                     // SS = [A, B, D]
        ...
        }                    // SS = [A, B] → D() 함수 호출이 끝나서 pop
  }                          // SS = [A] → B() 함수 호출이 끝나서 pop
}                            // SS = [] → A() 함수 호출이 끝나서 pop

 

 

# 재귀문과 반복문의 관계

- 모든 재귀문으로 작성된 프로그램은 반복문으로 다시 작성할 수 있음

- 반복문 문법을 제공하지 않는 함수형 언어에서는 재귀 호출 방식으로 프로그램을 작성

- 재귀문보다는 반복문 사용을 권장하는 이유

> 재귀 호출은 새로운 함수를 호출하는 것이기 때문에 함수를 호출할 때마다

시스템 스택에 활성 레코드가 쌓임. 따라서 너무 많은 횟수의 재귀호출을 할 경우

메모리가 부족하게되는 스택 오버플로우 현상 발생

> 반복문은 단순 명령어를 반복 실행하는 것이므로 무한 루프에 빠지더라도

스택 오버플로우는 발생하지 않음

 

 

 

 

 

 

 

---

[활성레코드] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kkpa1002&logNo=20106293058

[함수호출과정] https://foxtrotin.tistory.com/262

[시스템 스택] https://minwook-shin.github.io/system-stack/

​