Concept : 재귀(Recursion)의 기본 개념 이해하기

재귀(Recursion)의 기본 개념 이해하기

이 글에서는 기존에 반복문으로 해결하던 문제를 재귀적 사고로 해결할 수 있다는 것을 알아봅니다. 재귀함수를 구성하는 기본적인 논리와 재귀함수를 구현할 때의 주의점에 대해 짚어봅니다.

재귀적(recursive) 호출이란?

---

재귀를 wikipedia를 찾아보면 자기 스스로를 참조하는 것이라고 정의되어있습니다.
스스로를 호출하는 함수(메서드)라고 보아도 무방할 것 같습니다.

왜 스스로를 호출하느냐? 그것은 문제가 해결될 때까지 특정 동작을 반복하기 위해서입니다.

근데, 여기쯤 왔다면 우리는 이미 반복을 위한 도구를 가지고 있죠. for와 while로 대두되는 반복문입니다.

반복문도 반복을 위한 것이고, 재귀도 반복적인 동작을 위한 것이라면 둘의 차이는 무엇이 있을까요?
그것은 재귀함수의 기본적인 형태를 보고 나서 좀 더 쉽게 이해할 수 있을 것 같습니다.

재귀의 기본 형태

---

재귀의 기본적인 형태는 아래와 같습니다.

public static void main(String[] args) {
    String returnString = recursive(5); // 재귀함수(메서드) 호출부

    System.out.println(returnString); // "12345"
}

/* 재귀함수(메서드) */
public static String recursive(int i) {
    if (i == 1) { /* base case */
        return "" + i; // "1"
    }

    return recursive(i - 1) + i; /* 재귀적 호출 */
}

재귀로 구현된 메서드도 일반적인 메서드와 동일한 형태를 가지고 있습니다. 다만 특징을 몇가지 찾을 수 있지요.
그 특징은 다음과 같습니다.

1. 내부에서 스스로를 호출하는 부분이 있어야 한다.
   • 위 코드에서 '재귀적 호출'이라고 주석한 부분이 보이시나요? 메서드 자신을 호출하고 있습니다. 이렇듯 반복적으로 자기 자신을 호출해야지만 당연히 재귀함수가 되는 것이겠죠?
2. base case가 있다.
   • 반복문에는 조건식이 있어서 조건식이 true를 나타낼 동안 루프를 돌죠. 다시 말해서 반복문의 조건식은 수행될 조건을 명시하는 식이에요.
   • 위 코드에서 base case라고 주석처리된 if문이 보이시나요? 이 부분이 재귀함수의 조건식입니다. 보통은 베이스케이스base case라고 불려요. 반복문의 조건식과 다른 점은, 재귀함수의 조건식은 대개 탈출 조건이 명시된다는 점입니다.
   • 재귀함수는 내부에서 자기 자신을 호출하기 때문에, 탈출 조건이 없으면 무한히 자기 자신을 호출하게 됩니다. 조건식이 없는 반복문이 무한 루프에 빠지듯이 말이죠!
3. 재귀함수는 호출될 수록 base case에 수렴해야 한다.
   • 위 코드에서는 i == 1이면 재귀호출을 멈추고 리턴하도록 강제하고 있죠. 최초로 호출하는 메인 메서드에서는 i값으로 10을 넘겨주고 있습니다.
   • 그런데 만약에, 최초로 넘겨준 10이란 값이 점점 줄어들지 않고, 재귀를 거칠수록 1씩 커진다고 해볼게요.
   • recursive(10)... recursive(11)... recursive(12)...... recursive(100)............ recursive(1000000)... 이렇게 재귀호출은 끝나지 않고 호출될 거에요. 스택오버플로우가 발생하기 전까지 말이죠!
   • 그래서 위 코드의 '재귀적 호출' 주석 부분의 코드를 보면, i값이 매번 1씩 감소되도록 하고 있습니다. i == 1이라는 base case에 가까워지도록요.
   • 만약 베이스케이스를 i == 100과 같은 식으로 구성한다면 어떨까요? 이전과 똑같이, 호출할때마다 -= 1 해주면 될까요? 아니죠. 초기값이 10이니까, 100에 가까워지려면 점점 커져야 할 겁니다.
   • 계속해서 강조하지만 가까워져야합니다. 지나쳐서도 안되겠죠?!

주의할 점

---

사실 위에서 다 언급이 된 것 같아요.

• 반드시 base case가 존재해야 하고
• 재귀로 넘겨지는 파라미터는 반드시 base case로 수렴해야만 한다는 것입니다.
• 그리고 메서드 호출이기 때문에, 콜스택 제한에 걸리거나(존재한다면), 오버헤드가 발생할 수 밖에 없다는 것을 염두해야 합니다.

---

반복문과 마찬가지로 훨씬 더 복잡한 기능 구현이 가능하니 많은 케이스를 실습해보아야 할 것 같습니다.
모든 반복문은 재귀함수로 대치할 수 있어요. 형태가 많이 낯설 수 있지만, 반복문을 이해하고 사용하시는 분이라면 누구나 재귀에 익숙해질 수 있다는 뜻이겠죠! 많이 써서 익숙해지면 좋겠습니다.
화이팅!