자바스크립트로 구현하는 재귀함수, 재귀호출

패스트캠퍼스 코딩테스트 강좌의 잔재미코딩 님 부분을 참고하였습니다.

재귀함수

recursive call

함수 안에서 동일한 함수를 호출하는 형태

팩토리얼 구현

1! = 1
2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4
n! = n * (n-1)!

const factorial = n => {
  if (n > 1) {
    return n * factorial(n - 1);
  } else {
    return n;
  }
};

console.log(factorial(1)); // 1 
console.log(factorial(2)); // 2
console.log(factorial(3)); // 6
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120

시간복잡도

n의 2제곱

재귀 호출의 일반적인 형태

// 1)
const func = 입력값 => {
  if (입력값 > 일정값) { // 입력이 일정값 이상이면
    return func(입력값 - 1) // 입력보다 작은 값
  } else {
    return 일정값, 입력값, 다른 특정값 // 재귀호출 종료
  }
}

// 2)
const func = 입력값 => {
  if (입력값 <= 일정값) { // 입력이 일정값보다 작거나 같으면
    return 일정값, 입력값, 다른 특정값 // 재귀호출 종료
  }
  return func(입력보다 작은 값);
}

2번째 형식으로 팩토리얼 예제를 다시 구현해보면

const factorial = n => {
  if (n <= 1) {
    return n;
  }
  return n * factorial(n - 1);
};

console.log(factorial(1)); // 1 
console.log(factorial(2)); // 2
console.log(factorial(3)); // 6
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120

재귀호출은 스택의 전형적인 예다

재귀호출 예시

예제 1) 1부터 n까지의 곱이 출력되게 하라.

const multiple1 = n => {
  if (n <= 1) {
    return n;
  }
  return n * multiple1(n - 1);
};
console.log(multiple1(10)); // 3628800

예제 2) 숫자가 들어있는 배열이 주어졌을 때, 배열 요소들의 합을 구하여라

const sum = array => {
  if (array.length <= 1) {
    return array[0];
  }
  const first = array.shift();
  return first + sum([...array]);
};

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(sum(array)); // 55

spread 문법 복습

예제 3) 회문 palindrome을 판별할 수 있는 함수를 만들어라. (eye, madam, level 처럼 거꾸로 읽어도 제대로 읽혀지는 것)

const palindrome = str => {
  // 해당 문자열의 길이가 1이거나 0이면(처음부터 0, 1이거나 회문 검사를 끝까지 통과했거나)
  if (str.length <= 1) {
    return true;
  }
  // 배열(문자열)의 길이 -1 이면 마지막 인덱스
  const lastIndex = str.length - 1;

  // 첫 글자와 마지막 글자가 같으면
  if (str[0] === str[lastIndex]) {
    // (동일한) 첫 글자와 마지막 글자를 제외한 글자를 다시 회문 검사
    return palindrome(str.slice(1, lastIndex));
  } else {
    // 검사 도중 첫 글자와 마지막 글자가 같지 않으면 false
    return false;
  }
};

console.log(palindrome("madam"));

예제 4) 정수 n에 대해 n이 홀수면 3 * n + 1을 하고 n이 짝수면 n을 2로 나눈다. 이를 n이 결국 1이 될 때까지 반복한다. n을 입력받아 n이 1이 되는 과정을 모두 출력하는 함수를 작성하세요.

const oneMaker = n => {
  console.log(n);
  if (n === 1) {
    return n;
  }
  if (n % 2 !== 0) {
    // 홀수
    // parseInt(정수로변환할대상, n진법)
    return oneMaker(parseInt(3 * n + 1, 10));
  } else {
    // 짝수
    return oneMaker(parseInt(n / 2), 10);
  }
};

oneMaker(3);

예제 5) 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

예)

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

const func = n => {
  // 규칙성이 발견되지 않는 경우들.
  if (n === 1) {
    return 1;
  } else if (n === 2) {
    return 2;
  } else if (n === 3) {
    return 4;
  }

  // 규칙성 시작
  return func(n - 1) + func(n - 2) + func(n - 3);
};

console.log(func(6));

예제 6) 피보나치 수열

0번째 항은 0, 1번째 항은 1, 그다음부터는 전전번 항과 전번 항을 합.

const fibo = n => {
  if (n <= 1) {
    return n;
  } else {
    return fibo(n - 1) + fibo(n - 2);
  }
};