[JS] - 재귀

→ Open in Slid

• 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.

---

재귀는 단순히 중첩된 함수 호출이다. 모든 중첩된 함수에서 가장 내부에 중첩된 함수가 가장 먼저 반환됩니다.

해당 블로그를 참조하면, 이 부분을 이해하는 것이 매우 중요하다고 한다. '처음 보자마자 이해가 되지 않았다면, 이 부분을 몇번 읽어보세요'라고 강조할 정도로.

1. 팩토리얼 예제

factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)
factorial(0) returns 1
// 여기서 기반 조건이 충족됩니다. 재귀 함수는 안에서 부터 바깥으로 값을 반환해나갑니다.
factorial(0) returns 1                 => 1
factorial(1) returns 1 * factorial(0)  => 1 * 1
factorial(2) returns 2 * factorial(1)  => 2 * 1 * 1
factorial(3) returns 3 * factorial(2)  => 3 * 2 * 1 * 1
// 3 * 2 * 1 * 1 = 6

이렇게 factorial(0)부터 ~ factorial(3)까지 값을 반환해 나간다.

이 말은, 3 -> 0이 아니고 / 0 -> 3으로 값을 반환한다는 뜻

2. 문자열 뒤집기 예제

function revStr(str) {
  if (str === '') return '';
  return revStr(str.substr(1)) + str[0];
}

revStr('cat')
// tac

다음과 같은 코드가 있습니다.

작동방식을 살펴보면

revStr('cat')  returns revStr('at') + 'c'
revStr('at')   returns revStr('t') +  'a'
revStr('t')    returns revStr('') +   't'
revStr('')     returns          

이제, 여기 중첩된 함수 호출들이 있습니다. 중첩된 함수 호출을 갖고 있을 때, 가장 안쪽 함수가 가장 먼저 실행됩니다. 계속 리턴을 하며, 쌓인 재귀를 풀어나가기 시작하는 과정입니다.

revStr('')     returns                ''  => ''
revStr('t')    returns revStr('') +   't' => '' + 't'
revStr('at')   returns revStr('t') +  'a' => '' + 't' + 'a'
revStr('cat')  returns revStr('at') + 'c' => '' + 't' + 'a' + 'c'
// tac

이런식으로, 재귀 함수는 안쪽에서 바깥쪽으로!! return한다.