[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)
{
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

// 출력 결과
// #
// ##
// ###
// ####

draw 함수는 높이를 입력받아 중첩 루프를 통해 피라미드를 출력한다.

 

바깥쪽 루프는 안쪽 루프에서 수행하는 내용을 반복하도록 해줄 뿐이다. 바깥쪽 루프를 없애고 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");
}

 

// 출력 결과
// #
// ##
// ###
// ####

 

동작 원리:

1. h 높이를 받으면 h-1 높이로 draw 함수를 먼저 호출
2. 그 이후에 h만큼 '#'을 출력
3. 내부적으로 호출된 draw 함수를 따라가다가 h == 0이 되면 종료

 

재귀 호출 순서 (h=4일 때):

draw(4)
  → draw(3)
    → draw(2)
      → draw(1)
        → draw(0) [종료]
        → # 출력
      → ## 출력
    → ### 출력
  → #### 출력

재귀를 사용하면 중첩 루프 없이 하나의 함수로 동일한 작업을 수행할 수 있다.

 

재귀의 구성 요소

1. 기저 조건 (Base Case)

if (h == 0)
{
    return;
}

재귀를 멈추는 조건을 말하며, 기저 조건이 없으면 무한 재귀가 발생한다.

 

2. 재귀 호출 (Recursive Case)

draw(h - 1);

자기 자신을 호출하되, 기저 조건에 가까워지도록 변경한다.

 

연습 문제

Q. 반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 무엇일까?
재귀의 장점:

1. 간결성
   • 복잡한 구조를 간단하게 표현
   • 코드가 짧고 이해하기 쉬움
2. 가독성
   • 문제의 정의와 코드가 일치
   • 수학적 정의를 그대로 코드로 표현 (예: 팩토리얼, 피보나치)
3. 자연스러운 표현
   • 트리, 그래프 등 재귀적 자료구조에 적합
   • 분할 정복 알고리즘에 유용
4. 특정 문제에서 성능 우수
   • 메모이제이션과 결합 시 효율적
   • 일부 알고리즘은 재귀가 더 빠름

재귀의 단점:

1. 메모리 사용
   • 함수 호출마다 스택 메모리 사용
   • 깊은 재귀는 스택 오버플로우 위험
2. 성능
   • 함수 호출 오버헤드
   • 일부 경우 반복문보다 느림

 

결론:
재귀는 코드의 명확성과 간결성을 높이며, 특정 문제(트리 순회, 분할 정복 등)에서는 필수적이다.
상황에 맞게 재귀와 반복문을 선택하는 것이 중요하다.