재귀


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을 리턴한다.