[자료구조] 재귀(Recursion)

어떤 함수를 쓰다보면, 이걸 함수 내에서 또 써야하는데?? 하는 상황이 생길 수 있습니다.

이런 경우 for문과 while문으로 적절히 버무리면 구현이 가능하지만, 보다 이해하기 쉽고 빠르게 구현할 수 있는 또 다른 방법이 존재하는데, 바로 재귀함수(Recursion Function) 입니다!

0. 재귀가 뭔데??

재귀란 자기 자신을 다시 호출하는 것을 의미합니다.

아래 코드를 보면 아주아주 쉽게 이해하실 수 있습니다.

void recursion (x) {
	recursion(x);
{

그런데, 코드에서 약간 이상한 느낌이 들지 않나요?

위 코드를 그대로 돌리게 되면 자기 자신을 무한히 호출하는 상황이 발생합니다.

마치 while(1)을 돌린 것과 같은 효과가 발생한다고 보시면 됩니다!

그렇다면 이런 무한루프를 탈출하기 위해서는 어떻게 해야할까요?

바로 Base case라는 탈출 조건이 필요하게 됩니다.

Base case에 도달하는 순간 반복(Recursive)이 멈추게 되는 것이죠.

위 사진에서는 x가 점차 줄어들다가 결국 0에 가까워지고, return을 통해 함수가 종료된다는 것을 확인하실 수 있습니다.

이렇게 자기 자신을 호출하는 경우를 General case라고 부르고, 재귀 함수의 호출이 멈추는 경우를 Base case라고 부릅니다.

다만 위 예시에서는 x가 음수로 시작하는 경우 x는 무한히 작아지면서 함수가 끝나지 않는다는 문제점이 존재합니다. 그렇기 때문에 Base case를 설정할 때는 반드시 검증 과정이 필요합니다!!

Recursive의 가장 대표적인 예시는 팩토리얼입니다. 3! = 2! * 3 이고, 4! = 3! * 4죠?? 이걸 일반화하면 n! = (n-1)! * n이라는 것을 알 수 있습니다.

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

Resursive Function을 만들 때는 Base case / General case / Smaller caller 라는 총 세 가지의 질문을 자신에게 던져야 합니다.

복습차원에서 각각이 어떤 내용인지를 간단하게 살펴보면 다음과 같습니다.

또한 재귀함수에는 Head Recursion(머리재귀)과 Tail Recursion(꼬리재귀)가 존재합니다.

보통은 이해하기 쉬운 Tail Recursion을 많이 사용하지만, Head Recursion도 잘 알아둘 필요가 있습니다. (내가 써먹지는 못하더라도 적어도 다른 분들이 만든 함수는 이해해야 하니까..)

마지막으로 Recursion으로 표현할 수 있는 요소들은 Iteration으로도 표현할 수 있습니다.

Recursion 방식과 Iteration 방식으로 각각 피보나치 수열을 만들면 아래와 같습니다.