재귀(Recusion) 함수? 재귀 호출(Recusive Call)?

정의

자기 자신을 재참조하는 기법을 의미한다.

 

단순 반복문을 재귀 형태로 구현할 수 있다.

반대로 재귀 형태를 단순 반복문 형태로도 바꿀 수 있다. (반복문 ↔ 재귀호출)

 

예시

팩토리얼로 구현해야 한다고 가정해보시자.

ex) factorial(3) = 3 × 2 × 1 = 6 을 구하는 과정

 

반복문 Ver.

#include <stdio.h>

int factorial(int x)
{
       int ret = 1;
       for (int i = 1; i <= x; ++i)
       {
              ret *= i;
       }
       return ret;
}

int main()
{
       printf("%d\n", factorial(3)); // 6
}

 

재귀호출 Ver.

#include <stdio.h>

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

int main()
{
       printf("%d\n", factorial(3)); // 6
}

 

정리

재귀 사용에 있어서 주의할 점은 "종료 조건"을 잊어서는 안된다.

break; return;와 같은 종료 조건이 명확하지 않은 경우

무한 루프에 빠질 수 있다. 🤦‍♂️

 

구현 Case나 사람에 따라 다르겠지만 재귀형태보다는 단순 반복문이

코드 볼 때, 대부분 가독성이 높다고 한다.

잘못 사용하면 스택 call 반복적으로 쌓여 성능에도 영향을 줄 수 있기에

성능이나 가독성 측면에서도 실무에서는 재귀함수는 잘 사용하지 않는다.

 

오류가 발생했을 때, 디버깅 하는 것도 쉽지 않다.

그렇기에 코딩 테스트에 있어서도 재귀함수 구현보다는 

반복문 형태로 우선적으로 구현하는 것을 추천한다.

 

Q) 그렇다면 왜 재귀함수가 필요하고 언제 사용할까라는 의문이 든다.

- 구현 알고리즘이 재귀적으로 표현하는 것이 보다 자연스러운 경우.

    ex) 동적계획법(Dynamic Programming, DP) 

- 사용하는 변수 개수 줄이기 위해.