[Algorithm] 재귀 함수를 스택과 반복문으로 구현하기

개요

모든 재귀함수는 스택과 반복문으로 구현할 수 있다. 다만, 난이도가 높기 때문에 시도하기 어렵다.

이 포스팅에서는 재귀함수를 스택과 반복문으로 구현하는 방법에 대해 다룬다.

 

구현 - Tail Recursion

먼저 상대적으로 쉬운 Tail Recursion을 스택으로 변환해보자.

예제로 사용될 알고리즘은 이진 탐색이다.

int binarySearch(const std::vector<int>& arr, int target) 
{
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) 
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) 
            return mid;
        else if (arr[mid] > target) 
            right = mid - 1;
        else 
            left = mid + 1;
    }

    return -1;
}

 

 

스택을 이용하여 구현한다면 다음과 같이 구현할 수 있다. 일반적으로 꼬리 재귀를 스택으로 구현하는 것은 어렵지 않다.

int binarySearch(const std::vector<int>& arr, int target) 
{
    std::stack<std::pair<int, int>> stack;
    stack.push({0, arr.size() - 1});

    while (!stack.empty()) {
        int left = stack.top().first;
        int right = stack.top().second;
        stack.pop();

        if (left <= right) 
        {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) 
            {
                return mid;
            }
            if (arr[mid] > target) 
            {
                stack.push({left, mid - 1});
            }
            else 
            {
                stack.push({mid + 1, right});
            }
        }
    }

    return -1;
}

 

 

구현 - General Recursion

다음으로 일반적인 재귀함수를 스택으로 구현해보자. 

예제로 사용할 재귀함수는 재귀 함수 내에 반복문이 있는, 난이도가 있는 예제로 선택하였다.

재귀함수를 스택으로 구현하기 위해서는 재귀함수 내부의 모든 실행 블럭들을 구분지어야한다.
디버깅이 용이하도록 각 영역에서 값을 출력하도록 한다.

static void F1(int n)
{
	std::cout << n << " " << 1 << std::endl;
	if (n == 0)
	{
		std::cout << n << " " << 2 << std::endl;
		return;
	}

	std::cout << n << " " << 3 << std::endl;

	for (int i = 0; i < n; ++i)
	{
		std::cout << n << " " << 4 << std::endl;
		F1(n - 1);
		std::cout << n << " " << 5 << std::endl;
	}

	std::cout << n << " " << 6 << std::endl;
}

 

함수의 특성을 생각해보자. 함수는 호출될 때, 자신의 상태를 저장하기 위한 고유 스택을 생성한다. 스택에 값이 저장되어 있기 때문에, 함수 내에서 다른 함수를 호출하여 프레임을 벗어나더라도, return을 통해 해당 위치로 돌아오면 그 값을 꺼내어 실행을 재개할 수 있다. 물론 함수의 스택 프레임을 잡는 것은 운영체제가 알아서 해주지만, 여기에서는 직접 자료구조 스택을 이용하여 해본다.

 

상태를 저장하는 기능은 스택을 이용한다면 쉽게 구현할 수 있다. 어떤 작업을 실행중에 함수호출이 발생하면, 현재까지 작업중이던 내용을 스택 프레임에 저장하고 함수호출이 끝날 때 "해당 위치부터 실행을 재개하면 된다". 하지만 어떻게 해당 위치부터 작업을 재개할 수 있을까? 이를 표현하기 위해 실행 흐름의 각 구간을 나누고, 상태값을 스택 프레임에 추가적으로 넣어서 흐름을 컨트롤한다. 즉, 스택 프레임을 통해 상태를 재구성하고, phase 변수와 loop를 이용하여 흐름을 컨트롤한다. 흐름 컨트롤을 구현하기 위해 phase라는 변수와 switch case문을 이용할 것이다. 스택이 최종적으로 빌 때까지 위 과정을 반복해야 하므로 while loop으로 전체 작업을 반복한다. 

스택 프레임에 들어갈 변수도 정해야한다. 일반적으로 다음과 같이 정의한다.

재귀함수의 모든 파라메터 + 재귀함수의 모든 로컬 변수 + phase 변수

 

구현을 시작해보자.

static void F2(int n)
{
	// 재귀함수 파라메터 N, phase, 재귀함수 로컬변수 i
	std::stack<std::tuple<int, int, int>> stk;

	// 시작 상태를 넣어 반복문을 실행시킨다.
	stk.push(std::make_tuple(n, 0, 0));

	while (!stk.empty())
	{
		// 스택 프레임의 레퍼런스를 참조하여 보다 쉽게 흐름 컨트롤을 수행할 수 있다.
		std::tuple<int, int, int>& t = stk.top();
		int current_n = std::get<0>(t);

		// phase와 i는 스택 프레임 속에 존재하면서도 값이 바뀌어 반복문의 흐름을 컨트롤하는 역할을 수행한다.
		int& phase = std::get<1>(t);
		int& i = std::get<2>(t);

		// phase를 통해 재귀함수 내 실행 흐름을 구간 단위로 컨트롤한다.
		switch (phase)
		{
		case 0:
			// 재귀함수 시작 시 수행하는 작업을 phase 0에서 수행한다.
			std::cout << current_n << " " << 1 << std::endl;
			if (current_n == 0)
			{
				// 재귀함수의 끝 조건 시 수행할 작업, 재귀함수의 끝을 표현하기 위해 stack에서 원소를 제거한다.
				std::cout << current_n << " " << 2 << std::endl;
				stk.pop();
				continue;
			}

			std::cout << current_n << " " << 3 << std::endl;

			// 다음 실행 흐름은 for loop로 들어가기 때문에 구간이 분리되어 있다.
			// phase를 1로 변경하면 스택 프레임(튜플의 두번째 원소) 값이 변경되고,
			// 값이 변경된 채로 while loop를 통해 1번 흐름으로 건너갈 수 있다.
			phase = 1;
			break;

		case 1:
			// 반복문에 진입 시 수행할 작업을 수행한다.
			std::cout << current_n << " " << 4 << std::endl;

			// 반복문 내 함수를 재귀적으로 호출하는데, 이를 표현하기 위해 새로운 스택 프레임을 생성한다.
			stk.push(std::make_tuple(current_n - 1, 0, 0));

			// 현재 스택 프레임의 phase를 2로 세팅해둔다. 
			// while loop을 다시 만나면 위에서 추가된 새로운 스택 프레임이 세팅되며,
			// 이는 현재까지의 작업을 재귀적으로 표현한다.
			// 상위의 모든 작업들이 끝난 후 stack pop이 수행되면 다시 현재 스택 프레임을 만날 것이고,
			// 그러면 phase 2를 통해 2번 흐름으로 건너간다.
			phase = 2;

			break;

		case 2:
			// 2번 흐름은 반복문 내 재귀 이후 작업을 표현한다.
			std::cout << current_n << " " << 5 << std::endl;
			i++;

			// i의 값에 따라 실행 흐름을 어디로 보낼 지 결정한다.
			if (i < current_n)
			{
				phase = 1;
			}
			else
			{
				phase = 3;
			}
			break;

		case 3:
			// 현재 프레임에서의 작업은 모두 끝났으므로, 현재 프레임을 스택에서 제거한다.
			std::cout << current_n << " " << 6 << std::endl;
			stk.pop(); // remove the current frame
			break;
		}
	}
}

 

 

p.s

성능 최적화할 일이 생겨서 재귀를 스택으로 바꾸면 빨라지지 않을까? 하는 생각으로 구현을 시작했는데.. 

막상 다 구현해놓고 보니 오히려 느려졌다. 시간이 남을 때 한번쯤 구현해보면 좋을 듯 싶다.