JS - 재귀함수

재귀 함수

다시 나를 호출한다라고 생각하면 편한데 f()라는 함수가 있다면 이 f()함수 내부에서 또 자기 자신을 f()함수로 부르는 것이다.

바로 예시를 살펴보자

function makeArray(n) {
  if (n === 1) return [1];
  return [...makeArray(n-1), n]
};
makeArray(10);

위 코드는 1~10까지 원소로 이루어진 배열을 만드는 재귀함수이다.

동작흐름을 저번 실행컨텍스트를 따라 순서대로 나열하자면

• 전역 평가 : makeArray라는 함수 <f.o>가 만들어지고 테이블에 등록된다
• 전역 실행 : makeArray에 arguments로 10을 넘겨주며 실행한다
• makeArray 함수 평가 : if의 블럭은 EnvironmentRecord가 만들어는지겠지만 아무것도 가지고 있지는 않다. 파라미터로 쓰일 n을 미리 지정해놓는다(UIY)
• makeArray 함수 실행 : n에 arguments로 전달받은 10을 할당하고 진행하는데 return에 makeArray(n-1)이 있으므로 잠시 실행컨텍스트는 멈춘채 makeArray(n-1)을 실행한다. 이는 n이 10이기에 10-1인 makeArray(9)가 실행 컨텍스트에 올라간다.
• 이후로 makeArray(8),makeArray(7),....,makeArray(1)까지 실행컨텍스트에 올라간다.
• 이는 return값이 재귀로 인해 물리고 물렸기 때문이며 n에 1이 할당되었을 때 드디어 if문을 만나 return [1]이 실행되어 다시 역순으로 리턴값을 전달하고 마지막에 우리가 원하는 배열을 받을 수 있다

이처럼 스스로를 계속 꼬리물듯이 다시 부르는 것을 재귀함수라고 한다

재귀함수를 만들때 가장 중요한 부분으로는 종료 조건을 만들어놔야 되는 것이다
결국 재귀함수는 반복문과 비슷하다고 볼 수 있으며 이로인해 종료조건을 만들지 않을 경우 무한 실행되어 stack overflow가 일어나게 된다.

꼭 종료 조건을 가장 먼저 만들 수 있도록 하자