재귀

2023. 03. 27.

10872번 (팩토리얼)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim();
const inputNum = parseInt(input);

function factorial(num) {
  if (num <= 1) {
    return 1;
  }
  return num * factorial(num - 1);
}

console.log(factorial(inputNum));

n! = n * (n-1)! 이다. 이를 이용하여 재귀 함수를 이용해 구현했다.

자바스크립트로 재귀 함수를 구현해본 것은 처음이다. 문제가 복잡해지면 어려워질 것 같다.

간단하게 재귀함수와 반복문의 차이를 찾아봤는데 반복문이 시간, 메모리 면에서 더 효율적이지만 알고리즘 상 재귀함수를 사용하는 것이 더 자연스럽거나 코드의 길이를 확 줄일 수 있는 경우 재귀함수를 사용할 수 있다고 한다.

10870번 (피보나치 수 5)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim();
const inputNum = parseInt(input);

function fibo(num) {
  if (num == 0) {
    return 0;
  } else if (num == 1) {
    return 1;
  }
  return fibo(num-2) + fibo(num-1);
}

console.log(fibo(inputNum));

재귀 함수의 형식에 익숙해지는 과정인 듯 하다.

재귀에서 중요한 것은 스택 오버플로우가 발생하지 않도록 탈출구를 잘 지정하는 것이다.

25501번 (재귀의 귀재)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split('\n');
const T = input.shift();
let count = 0;

function recursion(s, l, r) {
  count++;
  if (l >= r) {
    return 1;
  } else if (s[l] != s[r]) {
    return 0;
  } else {
    return recursion(s, l+1, r-1);
  }
}

for (let i = 0; i < T; i++) {
  console.log(recursion(input[i], 0, input[i].length-1), count);
  count = 0;
}

재귀 함수를 수행하면 count가 1 증가하도록 하여 호출 횟수를 알아냈다.

이는 출력 후 다시 0으로 초기화한다.

recursion 함수는 팰린드롬이 맞으면 1을 출력하고 아니면 0을 출력한다.

s[l]이 s[r]과 다를 경우 0을 리턴하는데 l이 r보다 크거나 같을 때까지 0이 리턴되지 않으면 s[l]이 s[r]과 계속 같았다는 것이므로 1을 리턴한다.