cs50 4강 재귀

재귀

간단하게 설명하면 함수가 함수 자신을 호출하는 것이다.
아래의 예시 코드를 보면 재귀가 무엇인지는 이해가 잘 갈 것이다.

재귀 예시 코드

#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함수가 자기 스스로를 호출하는 부분이 재귀 호출 부분이다.

왜 써야할까?

재귀는 반복문으로도 충분히 대체가 가능하다.
그래서 코드로만 읽었을 때에는 왜 저렇게 독특한 형식을 사용해야하는지 의구심이 들 수 있다.

경제적

우선 코드를 작성함에 있어서 반복문을 사용하는 것보다는 재귀호출을 하는 쪽이 훨씬 경제적이다.
물론 지나치게 잦은 호출은 더 스파게티 코드가 될 수 있지만, 간결하게 표현 가능한 부분만 떼어 보자면 재귀 쪽이 더 경제적이다.

코드 재사용

위에서 작성한 변수를 재귀에서는 동일하게 사용가능하다.(본질적으로 본체를 공유하고 있으니 당연하다)
따라서 반복문을 다시 짜는 것보다는 코드의 재사용성이 높아진다.

주의점

재귀 호출을 너무 잦게 하게 되면 메모리에 무리가 오게 된다.
함수는 컴퓨터에게 일종의 행동과 같은 것인데, 컴퓨터는 원칙적으로 하나의 행동 밖에 하지 못한다.
그래서 재귀호출을 반복하게 되면 행동-복귀가 반복되면서 메모리에 무리가 갈 수 있다.

병합 정렬

병합 정렬은 우리가 1-3세션에서 배운 정렬들보다 훨씬 경제적이다.
굳이 재귀파트와 내가 함께 묶어서 게시물을 작성하는 이유는 위 정렬의 작동 방식이 바로 재귀적이기 때문이다.

작동법

병합 정렬은 재귀 함수와 똑같은 장단점을 가지고 있다.
즉 작동법도 유사하다는 것이다.
숫자를 쪼개서 순서를 정렬한 뒤 병합해내는 방식이다.

특이점

실행시간의 상한선과 하한선이 모두 동일하다.
그 이유는 정렬이 되어있든 안되어있든 우선 숫자들을 쪼갠 뒤 병합하는 과정을 무조건적으로 진행해야하기 때문이다.

단점

최악의 경우에는 병합정렬이 더 빠르지만, 운이 좋은 경우끼리 비교해보자면 병합정렬이 느리다.
또한 어쩔 수 없이 소비하는 메모리가 많아지면서 오버헤드 현상이 발생하게 된다.
오버헤드 현상이란

장점

상대적인 순서를 유지하는 특성 때문에, 대규모의 작업을 처리할 때 유리하다(근데 메모리는 많이 잡아먹으니까 유의하자)
또한 외부의 데이터를 정렬할 때에도 편하게 사용가능하다.