반복과 재귀

Goal

• 순환과 반복을 적절하게 사용할 수 있다.

---

프로그래밍 언어에서 어떤 일을 반복적으로 수행하는 방법으로 반복(iteration)과 재귀(recursion)가 있다.

 

반복과 순환, 두 가지의 방법에 대해서 알아보자

반복(iteration)

for, while 등의 반복 구문을 이용해서 특정 구문을 반복하는 방법

 

[반복 구현 코드]

int factorial(int n)
{
    int result = 1;

    for (int i = n; i > 0; i--)
    {
        result = result * i;
    }

    return result;
}

재귀(recursion)

함수가 자기 자신을 호출하는 반복 방법

[재귀 구현 코드]

int factorial(int n)
{
    if (n == 1) return 1;
    else return n * factorial(n - 1);
}

위와 같이 스스로를 호출하는 함수를 재귀 함수라 한다.

 

재귀함수를 사용할 때 종료 구문을 잊어버리면 stack overflow가 발생할 수 있으므로 종료 구문이 있어야한다.

 

재귀 함수는 더이상 처리할 작업이 없을 경우 종료되는데, 이때 '더이상 쪼개지지 않는' 작업들을 가리켜

기저 사례(base case) 라고 한다.

 

반복 vs 재귀

일반적으로 반복과 재귀는 다음과 같은 차이가 있다. (반드시는 아님)

속도 : 반복 > 재귀

가독성 : 반복 < 재귀

 

재귀적인 방법은 함수를 호출하는 방법이기 때문에 일반적으로 반복에 비해 느리다.

=> call stack을 사용하면서 함수 관련 정보를 저장하는 작업을 해야 하기 떄문에 반복에 비해 overhead가 발생

 

재귀적인 방법으로 표현했을 때 사람한테 더 직관적인 경우가 많기 때문에 재귀적인 방법을 많이 사용한다.

 

재귀적 문제를 반복 구문으로 표현했을 때 복잡해질 수 있으므로 성능상 크게 이점을 보는 경우가 아니라면 재귀함수를 사용한다.

 

활용 예)

알고리즘 설명은 재귀 함수를 사용하고, 실제 코드는 반복을 사용해서 성능을 높인다.

(성능보다 가독성이 중요한 상황이라면 재귀 함수로 표현)

 

재귀는 문제를 유사한 형태의 여러 조각으로 쪼갠 뒤, 자신이 일부 조각에 대해 처리하고 나머지를 자기 자신을 호출해 실행하는 함수로, 여러 알고리즘 기법에 사용될 수 있는 유용한 방법이다.