[ JavaScript ]- 재귀함수

재귀: 원래의 자리로 되돌아가거나 되돌아오는 것을 뜻함

재귀함수는 자기 자신을 호출하는 함수를 말합니다.

function recursion () {
console.log("이것은")
console.log("재귀함수입니다.")
recursion()
}
//함수 recursion은 무한히 콘솔로그를 찍는 재귀함수입니다.

함수 recursion은 자기 자신을 끝없이 호출합니다. 이 함수는 그저 콘솔로그에 무한히 문장을 출력하는 딱히 써먹을 곳이 없는 함수일 뿐이지만, 재귀함수의 이런 특성을 잘 활용하면 반복적인 작업을 해야 하는 문제가 발생했을 때, 좀 더 간결한 코드로 해결할 수 있습니다.

 

재귀 함수를 언제 써야 할까요?

1. 어떤 문제가 비슷한 구조의 더 작은 문제로 나누어지는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
3. 반복문으로 해결할 수 있지만 조금 더 간결한 코드로 작성하고 싶을 경우

재귀 함수를 어떻게 써야 할까요?

• 해결하고자 하는 문제의 입력값과 출력값이 어떤 것인지 명확하게 구분하기
• 문제를 가장 작은 단위로 쪼개고 경우의 수를 나누어보기
• 문제의 가장 단순한 부분 해결하기 

재귀 함수를 활용해 해결하려는 문제의 입력값과 출력값을 먼저 정의함으로써, 도달하고자 하는 목표가 어떤 것인지 정확하게 파악할 수 있습니다. 이후에 문제를 어떻게 작은 단위로 나누어볼지 고민해보아야 합니다. 특정한 기준을 통해 문제의 크기로 구분이 가능하거나, 명확한 순서를 정할 수 있고 그 상황을 해결하는 방법이 동일할 경우 바람직한 단위로 문제를 구분했다고 할 수 있습니다.

이렇게 여러 경우로 구분한 뒤에 가장 단순하고 쉬운 부분부터 해결합니다. 이 부분이 재귀 함수의 기초(base case)가 됩니다.

이 base case를 통해 재귀 함수가 무한히 반복되지 않고 멈추는 기준인 탈출 조건을 만들 수 있습니다.

가장 쉬운 경우를 해결한 뒤에, 문제 상황을 구성하는 여러 가지 복잡한 경우의 수들을 처리해 줍니다.

 

재귀 함수의 특징

재귀 함수를 활용해 문제를 해결하는 방식은 위 그림과 같다고 할 수 있습니다.

같은 방법으로 해결할 수 있는 여러 가지 경우의 수를 특정한 기준에 따라 분류하고 이를 해결하는 과정에서 함수 자신이 또다시 호출되게 됩니다.

 

비유하자면 해결해야할 일을 그날그날 바로 처리하는게 아니라, 문제의 해결을 그 다음날의 자기 자신에게 미루는거라고 할 수 있습니다.(반드시 지양해야 할 태도이죠...)

아무튼 이러한 방식과 유사하게 재귀 함수 역시 가장 작은 단위의 문제가 해결될 때까지 상위 단계의 문제들이 해결되지 않습니다. 하지만 가장 단순한 문제가 해결되는 순간 그 결과를 활용해 단계적으로 모든 문제가 해결되는 구조입니다. 위 그림에서는 빨간색 네모에 해당하는 문제가 해결될 때, 도미노처럼 연쇄적으로 모든 네모들이 해결되게 됩니다.