FE RYAN
완벽하지 않으면 어때
FE RYAN
전체 방문자
오늘
어제

블로그 메뉴

  • 💾 깃허브 링크
  • 홈
  • 태그
  • 분류 전체보기 (151)
    • 개인프로젝트 (8)
      • 개인 포트폴리오 웹앱 (6)
      • 프론트엔드 기술면접 아카이빙 웹앱 (2)
    • 기록 (121)
      • 원티드 프리온보딩 인턴십 (0)
      • 코드스테이츠 프론트엔드 (75)
      • 생각들 (3)
      • Today I learned (32)
      • 회고 (9)
      • 리뷰 (1)
    • 개발 (17)
      • React (3)
      • Javascript (7)
      • CSS (1)
      • HTML (3)
      • HTTP (1)
      • 자료구조 (0)
      • 알고리즘 (2)
    • 코딩테스트 (2)
      • 백준 (2)
      • 프로그래머스 (0)
    • 디자인 (1)
      • UI & UX (1)
    • 수학 (0)
    • 자기계발 (0)

공지사항

인기 글

태그

  • 자바스크립트
  • 회고
  • 부트캠프
  • useMemo
  • 원시타입
  • 신입개발자
  • 프론트엔드
  • 딥다이브
  • css
  • seb39
  • ES6
  • Til
  • 메인프로젝트
  • 포트폴리오
  • HTML
  • 타입스크립트
  • 리액트
  • seb 39
  • 코드스테이츠
  • 자바스크립트 딥다이브

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
FE RYAN

완벽하지 않으면 어때

개발/알고리즘

자바스크립트로 설명하는 재귀함수

2022. 6. 1. 18:56
728x90

1. 재귀함수

  • 재귀: 자기 자신을 호출하는 절차.
  • 재귀 호출: 함수가 자기 자신을 호출하는 것.(recursive call)
  • 재귀 함수: 재귀 호출을 수행하는 함수. 즉 자기 자신을 호출하는 함수를 말한다.
  • 재귀 함수는 반복되는 처리 를 위해 사용한다. 주로 아래 경우에서 많이 사용한다.
    • JSON.parse() 를 호출하는 JSON.parse()
    • 팩토리얼
    • DOM 순회
    • 객체 순회
    • 자료구조 구현
  • 모든 경우에서 반복문을 대체함이 아닌, 재귀함수를 사용하는 것이 더 코드를 이해하기 쉬운 경우에 사용한다.
  • 탈출 조건이 없으면 무한반복 하여 스택 오버플로우 되므로 반드시 탈출 조건이 주어져야 한다! (탈출 조건: base case)
  • 반복되면서 입력받을 값 또한 계속 바뀌어야 한다. 그렇지 않으면 계속 같은 값만 확인하고 같은 결과만 받게 된다.
  • 콜 스택:
    • 자바스크립트에서 함수의 실행 순서를 결정하는 자료구조이다.
    • 스크립트가 함수 호출 → 인터프리터가 콜스택에 추가 → 함수 실행
    • 선입선출(FIFO) 방식이다.

1.1 재귀함수의 여러 형태

1.1.1 가장 기본적인 형태

function recursive(num) {
  if (num <= 0) {
    return console.log('탈출 조건에 걸려 재귀함수 종료.');
  }
  console.log(num);
  num--;
  recursive(num);
}
recursive(5);

// 5
// 4
// 3
// 2
// 1
// 탈출 조건에 걸려 재귀함수 종료.
  • 재귀 함수의 필수 구성요소: 1. 탈출 조건 (조건문, 비교할 값의 변화)
  • 재귀 함수는 탈출 조건(base case)이 없는 경우 무한반복되어 스택 오버플로우 현상이 발생된다.
  • 따라서 탈출 조건이 주어져야 하며, 반복 시마다 값 또한 변화되어야 계속 같은 값으로 같은 결과를 내는 것을 막을 수 있다.

1.1.2 반환값이 2번 등장한 형태

function sumOfAll(num) {
  if (num === 1) return 1;
  return num + sumOfAll(num - 1);
}
sumOfAll(3); // 6

/**
 * sumOfAll(3)
 *      return 3 + sumOfAll(2)
 *                  return 2 + sumOfAll(1)
 *                                  return 1
 */
  • 탈출 조건에서 반환값을 받아 마지막 재귀 호출의 반환값으로 하여 뎁스를 올라가며 최종적으로 재귀 함수 호출의 반환값을 반환하고 함수가 종료된다.
  • 즉 콜 스택에 쌓인 재귀 함수 호출이 탈출 조건을 만나면서 하나씩 실행되며 return value가 변화하면서 최종적으로 원하는 결과를 반환한다.

1.1.3 재귀 함수로 팩토리얼 구현하기

  • 팩토리얼: 주어진 수 부터 1까지 차례로 곱하기 ex: !4 = 4 * 3 * 2 * 1
// * 1. 반복문으로 팩토리얼 구현하기
function factorial(num) {
  let result = 1; // 초기값을 1로 주어야 *= 해서 값이 들어간다.
  for (let i = num; i > 0; i--) {
    result *= i;
  }
  return result;
}
factorial(4); // 24

// * 2. 재귀 함수로 팩토리얼 구현하기
function factorial(num) {
  if (num == 1) return 1; // 이 탈출 조건이 주어지지 않으면 무한반복.
  return num * factorial(num - 1);
}
factorial(4); // 24

1.1.4 헬퍼 메서드 재귀( = 헬퍼 함수인 재귀 함수)

function collectEvenNums(arr) {
  let result = [];

  function helper(changingInput) {
    if (changingInput.length === 0) return;

    if (changingInput[0] % 2 === 0) {
      result.push(changingInput[0]);
    }

    helper(changingInput.slice(1));
  }

  helper(arr);

  return result;
}

const arrInGlobal = [1, 2, 3, 4, 5, 6];

collectEvenNums(arrInGlobal); // [2, 4, 6]
  • 헬퍼 함수(보조 함수): 어떤 함수에서 호출되는 다른 함수. 외부 함수의 반환값으로 호출되거나, 외부 함수의 반환값 이전에 호출되어 외부 함수의 반환값을 의도대로 변경시킨다.

1.1.5 순수 재귀

  • 헬퍼 함수 없이 재귀 함수 안에서 재귀 호출만으로 구현되었다.
// * 순수 재귀

function collectEvenNums(arr) {
  // * newArr은 반복 할 때마다 빈 배열로 초기화된다.
  // * 하지만 arr이 재귀 호출시마다 slice된다.
  let newArr = [];

  if (arr.length === 0) return newArr;

  if (arr[0] % 2 === 0) {
    newArr.push(arr[0]);
  }
  // * 새 배열을 재할당하면서 concat 메서드 안에서 재귀 호출이 일어난다.
  newArr = newArr.concat(collectEvenNums(arr.slice(1)));
  return newArr;
}

const arrInGlobal = [1, 2, 3, 4, 5, 6];

collectEvenNums(arrInGlobal); // [2, 4, 6]

/**
 * [].concat(collectEvenNums([2,3,4,5,6]))
 *            [2].concat(collectEvenNums([3,4,5,6]))
 *                         [].concat(collectEvenNums([4,5,6]))
 *                                    [4].concat(collectEvenNums([5,6]))
 *                                                [].concat(collectEvenNum([6]))
 *                                                              [6]
 */

참고자료

  • 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스 링크
  • 모던 자바스크립트 딥 다이브 12장 - 함수
  • 콜스택이란 링크
728x90
저작자표시 비영리 변경금지 (새창열림)

'개발 > 알고리즘' 카테고리의 다른 글

DP(동적 프로그래밍) 자바스크립트 구현/ 작성중  (0) 2022.06.23
    '개발/알고리즘' 카테고리의 다른 글
    • DP(동적 프로그래밍) 자바스크립트 구현/ 작성중
    FE RYAN
    FE RYAN

    티스토리툴바