[알고리즘] 재귀(Recursion)와 콜 스택(Call Stack)

알고리즘 이론에서 기본이며, 분할 정복이나 백트래킹 같은 여러 알고리즘의 기반을 맡고 있는 재귀(recursion)는 무엇일까? 이에 대해 자세히 알아 보자.

 

인형 안에 더 작지만 같은 모양의 인형이 연이어 들어 있는 마트료시카를 떠올려 보자

 

📌 정의

  In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
  컴퓨터 과학에서, 재귀(Recursion)는 같은 문제를 좀 더 작은 예시로 나누는 것에 집중한, 컴퓨터적인 문제를 해결하는 방식 중 하나이다. 재귀는 코드 내에서 자신을 호출하는 함수를 이용하여 이러한 재귀적인 문제를 해결한다. 이러한 접근 방식은 다양한 형식의 문제에 적용될 수 있고, 재귀는 컴퓨터 과학에서 핵심적인 아이디어 중 하나이다.

Recursion (computer science) - Wikipedia

 

 

 

📌 작동 과정

재귀 함수의 작동 과정은 어떠한 함수가 특정 조건에 도달할 때까지 자기 자신을 계속 호출한다.

 

코드

# 재귀 함수 sum_ 정의
def sum_(n):
    # 종료 조건(Base Case): 만약 n이 1이면, 1을 반환
    if n == 1:
        return 1
    # 재귀 단계(Recursive Step): 종료 조건에 도달할 때까지 자기 함수를 계속 호출
    return n + sum_(n - 1)


# 테스트 코드
if __name__ == "__main__":
    # 매개변수에 5를 넣어 함수를 호출하고 화면 출력
    print(sum_(5))

 

이미지

재귀 함수가 작동하는 과정은 아래와 같다. 코드를 읽는 순서는 맨위부터 빨간 화살표를 따라 내려가서, 다시 맨아래부터 검은 화살표를 따라 올라오면 된다.

Recursion and its Types [with Examples] - Pencil Programmer

 

여기서,

1. 어떠한 함수의 특정 조건을 종료 조건(Base Case)이라 한다.
2. 종료 조건이 만들어지기 전까지 자기 자신을 계속 호출해 나가는 과정을 재귀 단계(Recursive Step)이라 한다.

 

📌 종료 조건(Base Case)

종료 조건은 주어진 함수를 직접 해결할 수 있는 경우이다.

• 따라서 재귀 함수에서 입력된 값이 먼저 종료 조건에 해당하는지를 먼저 확인해야 한다.
• 종료 조건에 해당하는 경우 함수를 직접 계산하여 원하는 값을 반환한다.
• 재귀 함수에서 최소한 하나의 종료 조건이 있어야 한다.

 

📌 재귀 단계(Recursive Step)

재귀 단계는 주어진 함수를 직접 해결할 수 없는 경우이다.

• 따라서 종료 조건에 도달할 때까지 해당 함수를 다시 호출한다.
• 만약 적절한 종료 조건이 없을 경우에는 끊임없이 자신을 호출하여 메모리 관련 문제가 발생(stack overflow)한다.

 

📌 콜 스택(call stack)

콜 스택을 설명하려면 다시 메모리 구조에 대해 잠깐 언급하고 넘어가야 한다. 이 중 스택에 대한 내용만 다룰 것이며, 자세한 내용은 운영체제를 공부할 때 설명하겠다.

 

(1) 메모리 구조

메모리는 주어진 데이터의 종류에 따라 해당 데이터를 구분하여 관리하는데, 크게 '4가지의 메모리 영역(코드, 데이터, 힙, 스택)'이 있다.

메모리의 구조, TCP School

 

(2)  스택 영역

여기서 함수(function)에 관한 데이터는 메모리 구조 중에서 스택(stack) 영역에서 관리한다.

 

(3) activation record / stack frame

실행된 프로그램(또는 함수)이 어떠한 함수를 호출할 경우, 호출된 함수에 대한 정보(지역 변수나 매개변수, 자기를 호출한 프로그램(또는 함수)의 반환 주소 등등)를 저장해야 한다. 이러한 호출 함수의 정보를 저장하는 연속적인 메모리 공간을 activation record 또는 stack frame이라 한다.

 

f 함수의 매개변수 p1, p2와 반환 주소(return address), 지역 변수 a[0]~a[3]와 x 등을 스택에 저장하고 있다.

activation record(또는 stack frame)의 예시

CSE 303 Lecture 10 - C memory model; stack allocation by Marty Stepp (published by Hans Månsson)

 

(4)  콜 스택(call stack)

이러한 activation record는 콜 스택(또는 호출 스택)이라는 공간에서 관리하게 된다. 함수를 호출하고 반환하는 과정이 후입선출(LIFO)의 특징을 갖고 있어서 자료 구조 중 스택이 가장 적절하다.

 

[자료구조] 스택(stack)에 대한 내용은 아래 참고.

[자료구조] 스택(stack) in Python

 

📌 스택 오버플로우(stack overflow)

재귀 함수가 종료 조건 없이 계속 자신을 호출하면 스택과 힙 사이의 이용가능한 메모리(available memory)를 넘어 힙(heap)까지 메모리 영역을 침범하는 스택 오버플로우(stack overflow)가 일어난다.

스택 오버플로우 이미지

Prevent and Mitigate Stack Overflow

 

재귀 함수에서 적절한 종료 조건이 없으면 왜 문제가 발생하는 것일까?

 

다른 메모리 영역도 마찬가지이지만 스택 영역은 무한하지 않다. 즉, 주소 공간의 한계가 있어서 유한한 범위를 지니고 있다. 콜 스택이 없어지지(pop) 않고 계속 해서 쌓이기(push)만 할 것이다. 결국에는 스택(stack)이 주소 공간의 한계를 넘어 넘치게(overflow)될 것이다.