13.7 재귀
재귀(resursion) 역시 널리 쓰이며 함수를 활용하는 중요한 패턴입니다.
재귀란 자기 자신을 호출하는 함수입니다.
같은 일을 반복하면서 그 대상이 점차 줄어드는 상황에서 재귀를 유용하게 활용할 수 있습니다.
먼저 건초 더미(haystack)에서 바늘(needle)을 찾는, 좀 인위적인 예제를 하나 봅시다.
실제로 건초 더미에서 바늘을 찾아야 하는 상황이라면 아마 이런 식으로 찾아볼 겁니다.
- 건초 더미에서 바늘이 보이면 3단계로 이동한다.
- 건초 더미에서 건초(hay)를 하나 덜어낸다. 1단계로 이동한다.
- 찾았다!
결국 바늘을 찾을 때까지 건초 더미에서 건초를 하나씩 제외하는 소거법이며, 이것이 재귀입니다.
이 행동을 코드로 바꿔 봅시다.
function findNeedle(haystack) {
if (haystack.length === 0) return "no haystack here!";
if (haystack.shift() === 'needle') return "found it!"
return findNeedle(haystack); // 건초더미에 들어있는 건초가 하나 줄었습니다.
}
findNeedle(['hay', 'hay', 'hay', 'hay', 'needle', 'hay', 'hay']);
이 재귀 함수에서 눈여겨볼 점은 모든 가능성을 전부 고려한다는 겁니다.
가능한 경우의 수는 haystack이 비어 있거나(찾을 대상이 없습니다), 배열의 첫 번째 요소가 바늘이거나(찾았습니다), 배열의 첫 번째 요소가 바늘이 아닌 경우입니다.
마지막은 배열의 어딘가에 바늘이 들어있을 테니 Array.prototype.shift로 배열의 첫 번째 요소를 제거하고 함수를 반복합니다.
재귀 함수에는 종료 조건이 있어야 합니다.
종료 조건이 없다면 자바스크립트 인터프리터에서 스택이 너무 깊다고 판단할 때까지 재귀 호출을 계속하다가 프로그램이 멈춥니다.
findNeedle 함수에는 두 가지 종료 조건이 있습니다.
바늘을 찾거나, 배열이 비어 있으면 재귀 호출을 멈춥니다.
호출할 때마다 배열의 길이가 줄어드므로 언젠가는 두 조건 중 하나를 만족하게 됩니다.
이번에는 좀 더 유용하고, 여러 번 검증된 예제를 살펴봅시다.
숫자의 계승(factorial)을 찾는 예제입니다.
숫자의 계승은 1부터 그 숫자까지를 전부 곱한 값이며 숫자 뒤에 느낌표를 붙여서 표시합니다.
즉 4!는 4 * 3 * 2 * 1 = 24 입니다.
계승을 구하는 재귀 함수는 다음과 같이 만들 수 있습니다.
function fact(n) {
if (n === 1) return 1;
return n * fact(n-1);
}
이 함수의 종료 조건은 n === 1이고, 재귀 호출할 때마다 숫자 n은 1씩 줄어들다가 결국 1이 됩니다.
이 함수에 0이나 음수를 넘겨서 호출하면 물론 에러가 생기지만, 그런 상황을 막을 조건문을 넣는 건 쉽습니다.
