알고리즘 | 재귀

✔ 학습목표

함수를 재귀적으로 사용하는 코드를 작성할 수 있다.

 

재귀

동일한 작업을 반복할 때는 사용자 정의 함수를 사용하면 보다 효율적으로 코드를 만들 수 있다고 배웠다. 하지만 함수 내에서 동일한 작업이 반복되는 경우에는 어떻게 해야 할까. 본 글에서는 함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 공부한다.

 

우리는 이제껏 int main(void){}안에서 프로그램을 작성하고 함수를 호출했다. 그런데 생각해보면 main()도 역시 함수이다. 함수 안에서 또 다른 함수를 사용해온 것이다. 이 사실을 알게 되면 함수가 본인 스스로를 호출해서 사용할 수 있는지에 대한 의문이 생긴다. 답은 할 수 있다 이다. 이를 재귀(Recursion)라고 한다.

 

#

##

###

####

#####

 

위와 같이 피라미드 모양을 출력하는 프로그램을 예로 들어보자.

 

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    // 사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");

    // 피라미드 그리기
    draw(height);
}

void draw(int h)
{
    // 높이가 h인 피라미드 그리기
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

 

프로그램에서는 get_int()를 사용해 높이를 입력받고, 사용자 정의 함수 draw()를 만들어 높이가 h인 피라미드를 출력했다. draw() 함수 내에서는 중첩 루프(for)를 사용했다. 이제껏 배운 내용으로 피라미드를 만들어야 할 때 가장 떠올리기 쉬운 방법이다.

 

그런데 여기서 draw()에 주목해보자. draw()내 중첩 루프에서 바깥쪽 루프는 안 쪽 루프에서 수행하는 내용을 반복하는데 쓰인다. 이는 draw()에서 바깥쪽 루프를 없애고 스스로를 '재귀적으로' 호출했을 때 똑같은 작업을 수행할 수 있다는 뜻이기도 하다.

 

코드를 수정하면 다음과 같다.

 

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

void draw(int h)
{
    // 높이가 0이라면 (그릴 필요가 없다면)
    if (h == 0)
    {
        return;
    }

    // 높이가 h-1인 피라미드 그리기
    draw(h - 1);

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

 

draw() 함수 안에서 draw() 함수를 호출하도록 만든 모습이다. draw() 함수는 h라는 높이를 받았을 때 h-1 높이로 draw() 함수를 먼저 호출한다. 그 후에 h만큼의 #을 출력한다.

 

처음에는 재귀함수의 개념이 잘 이해되지 않았다. 이게 어떻게 돌아가는 거지 라는 생각을 한참 했다. 그러다 코칭 스터디 게시판에 글을 남겼고, 재귀를 직관적으로 이해하기 위해서는 스택 프레임(stack frame)을 이해해야 한다는 답변을 받았다.

 

스택 프레임

메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역이다. 스택 영역은 함수의 호출과 함께 할당되고 호출이 완료되면 소멸한다. 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소 값, 함수에서 선언된 지역변수 등의 정보가 저장된다. 이렇게 스택에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 한다. 스텍 프레임이 있어 함수는 호출을 끝낸 뒤에 그 이전 상태로 돌아갈 수 있다.

 

간단한 예시 코드를 보자.

 

int main(void)

{

    func1();  // func1() 호출

    return 0;

}

 

void func1()

{

    func2();  // func2() 호출

}

 

void func2()

{

}

출처 TCP SCHOOL

 

Step 1. 프로그램이 실행되면 가장 먼저 main() 함수가 호출되어 main() 함수의 스택 프레임이 스택에 저장된다.

Step 2. func1() 함수를 호출하면 해당 함수의 스택 프레임이 스택에 저장된다.

Step 3. func2() 함수를 호출하면 해당 함수의 스택 프레임이 스택에 저장된다.

Step 4. func2() 함수의 모든 작업이 완료되어 반환되면 func2() 함수의 스택 프레임이 제거된다.

Step 5. func1() 함수의 호출이 종료되면 func1()함수의 스택 프레임이 제거된다.

Step 6. main()함수의 모든 작업이 완료되면 main() 함수의 스택 프레임이 제거되면서 프로그램이 종료된다.

 

이처럼 스텍은 가장 나중에 저장된 데이터가 가장 먼저 인출되는 방식으로 동작한다. 이러한 방식을 후입 선출(LIFO, Last-In First-Out) 방식이라고 한다. 스택은 푸시(push) 동작으로 데이터를 저장하고 팝(pop) 동작으로 데이터를 인출한다.

 

 

스택 프레임에 대해 공부했으니 앞선 재귀 함수의 예시를 다시 생각해보자. 

 

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

void draw(int h)
{
    // 높이가 0이라면 (그릴 필요가 없다면)
    if (h == 0)
    {
        return;
    }

    // 높이가 h-1인 피라미드 그리기
    draw(h - 1);

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

 

이 코드에서도 main()함수로부터 실행된 draw() 함수의 스택 프레임이 스택에 반복적으로 쌓인다. 예를 들어 입력값으로 5를 받았을 때 draw(5)에서부터 draw(1)까지 쌓이다 draw(0)이 되면 return을 통해 main()의 원래 위치로 돌아가는 것이다. 스택은 가장 나중에 저장된 데이터가 가장 먼저 인출되는 방식으로 동작한다고 앞서 말했다. 그러니 결과값은 가장 나중에 저장된 데이터, 즉 draw(1)에서 실행된 #에서부터 draw(5)에서 실행된 #####까지 스택에서 하나하나 빠지면서 만들어진다.

 

결과값

#

##

###

####

#####

 

 

출처 나무위키

하노이의 탑을 옆으로 옮긴다고 생각해보면 이해하기 쉬울 것이다.

 

 

 

 

 

재귀를 이해하는 데 있어 네이버 CS50 코칭 스터디 2기 WANNTE코치님께 도움을 받았다. 스택 프레임과 관련된 내용과 사진은 아래 사이트에서 가져왔다.

코딩교육 티씨피스쿨

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)