[CS50] 재귀

알고리즘을 구현하기 위해서 코드를 작성하다 보면 동일한 작업을 반복해야 할 때가 있는데 이런 작업을 함수로 구현하면 코드를 보다 효율적으로 만들 수 있었습니다. 하지만 함수 내에서도 동일한 작업이 반복되는 경우는 어떨까요? 오늘은 함수를 재귀적으로 호출하는 방법에 대해 공부해보도록 하겠습니다.

 

재귀란?

어떠한 것을 정의할 때 자기자신을 참조하는 것을 뜻한다.(출처 : 위키백과)

 

지금까지 main함수에서 함수를 호출해서 코드를 실행했었습니다. 이것을 다르게 말하면 함수 안에서 또 다른 함수를 사용할 수 있다 라는 말인데 그렇다면 함수가 본인 스스로를 호출해서 사용할 수도 있다는 말이 되고 이를 재귀라고 합니다.

 

지금까지는 아래와 같은 피라미드 모양을 출력하기 위해서

#

##

###

####

#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 함수를 정의했습니다.

그런데 이런 코드의 내용을 보면 결국 바깥쪽 루프는 안쪽 루프를 반복하는 코드입니다.

즉 높이 4의 피라미드는 높이 3의 피라미드에 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)
{
	if(h == 0)
    {
    	return;
    }
    
    draw(h-1);
    
	for(int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

이런식으로 높이 h를 받았을 때 h-1 높이로 draw함수를 먼저 호출하고 그 후에 h만큼의 #을 출력합니다. 이런 상황이 계속 반복되면 draw(-1), draw(-2).... 이런 상황이 발생할 수 있으므로 h = 0인 상황에 아무것도 하지 않는 조건문을 추가해줍니다.

이렇게 재귀함수를 사용하면 중첩 루프를 사용하지 않고 하나의 함수로도 동일한 작업을 수행할 수 있습니다.

 

 

그럼 for문대신에 재귀 함수를 사용할 때의 장점은 무엇이 있을까요?

사실 재귀 함수는 stack이라는 메모리 공간을 사용해 무한적으로 자기 자신을 부르면 메모리의 제한 때문에 stack overflow가 걸리게 될 것입니다. 그만큼 속도도 느리고요 그래도 사용하는 주된 이유는

1. 변수사용을 줄여줄 수 있다.

 

2. 가독성이 향상된다. 

입니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.