[JS] 재귀 함수

재귀(Recursion)

: 문제 해결을 위해 함수 자신을 다시 호출

• 문제 해결 능력이 자기자신에게 있음 👉 스스로를 호출함
• 어떤 프로시저(절차)가 자기 자신을 반복적 호출하여 문제를 풀어 나가는 알고리즘
• 함수 내부에서 함수를 호출하게 되면 먼저 호출됐던 함수가 일시정지 되고 호출된 함수가 실행된다.

function pow(x, n) {
  if (n === 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

pow(2, 3);

 

 

 

예시 1
factorial 함수를 재귀 호출 방식으로 작성

• 팩토리얼(n!): 그 수보다 작거나 같은 모든 양의 정수의 곱
  ex) 4! = 4 * 3 * 2 * 1

function factorial(n) {
  if (n === 1) {
    return n;

  } else {
    return n * factorial(n - 1)
  }
}

 

 

예시 2

fibonacci 함수를 재귀 호출 방식으로 작성

• 피보나치 수열: 처음과 두번째 항은 1이고, 그 뒤 모든 항은 바로 앞 두 항을 더한 합인 수열
  ex) 1, 1, 2, 3, 5, 8, ...

function fibonacci(n) {
  if (n <= 0) return 0;
  if (n <= 2) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2)
}

 

 

 

 

 

✨ 실행 컨텍스트(execution context)의 작동 흐름

1. 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조
2. 제어 흐름의 현재 위치, 변수의 현재 값, this 등을 저장
3. 함수가 호출될 때 마다, 하나의 실행 컨텍스트 생성
4. 내부에 중첩된 함수를 포함한 경우, 현재 함수의 실행 일시 중지
5. 중지된 함수와 연관된 실행 컨텍스트는 "실행 컨텍스트 스택" 자료 구조에 저장됨
6. 중첩 함수가 호출되어 실행됨 (호출 시 새로운 컨텍스트 생성)
7. 중첩 호출 실행이 종료되면 실행 컨텍스트 스택에서 일시 중단된 함수 실행 컨텍스트 꺼냄(pop)
8. 다시 중단되었던 함수의 실행을 이어감

 

 

 

📌 재귀 호출 알고리즘  vs  반복문 기반 알고리즘

• 재귀 호출 알고리즘: 재귀 깊이만큼 메모리가 필요
• 반복문 기반 알고리즘: 메모리가 절약됨

• 메모리 최적화 관점: 재귀 호출 > 반복문 기반 알고리즘에 비해 메모리 사용도가 높음
  - 작성하는 모든 곳에서 메모리 최적화가 필요한 것은 아니므로 가독성을 높이는 코드가 필요
• 재귀 호출은 코드를 짧게 만들고, 코드 이해도를 높이며 유지보수에도 이점이 있어 많이 사용됨

 

---

 

개발자 도구에서 코드 단계 별로 보기

 

 

---

 

재귀와 스택