[CS50] 알고리즘 - 재귀

재귀

함수를 사용할 때 주로 main 함수 안에서 필요한 순간에 호출하여 사용한다. 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");
    }
}

이 코드는 높이를 입력받아 중첩 루프를 통해 피라미드를 출력하는 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");
}

h라는 높이를 받았을 때 h-1 높이로 draw 함수를 먼저 호출한 후 h만큼의 #을 출력한다.

 

내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 된다.

 

이때는 아무것도 출력하지 않도록 조건문을 추가한다.

 

 

재귀 주의사항

재귀를 사용하면 중첩 루프를 사용하지 않고도 복잡한 반복문을 간결하게 만들 수 있다.

 

문제를 더 작은 문제로 나누어 해결하는 방식으로 접근할 수 있어 알고리즘 설계에 유용하다.

 

재귀는 잘못 사용하면 무한 루프에 빠질 수 있다. 따라서 설계할 때 종료 조건을 명확히 설정하는 것이 중요하다.

 

 

References

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

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