Javascript 재귀와 스택

📚 출처

https://ko.javascript.info/recursion

✍🏻 과제

1. 주어진 숫자까지의 모든 숫자 더하기

https://ko.javascript.info/task/sum-to

// 1. 반복문 사용
function sumTo1(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}
console.log(sumTo1(100)); // 5050

// 2. 재귀 사용하기
function sumTo2(n) {
  if (n == 1) {
    return n;
  } else {
    return n + sumTo2(n - 1);
  }
}
console.log(sumTo2(100)); // 5050

// 3. 재귀 사용하기 + 삼항 연산
function sumTo3(n) {
  return n == 1 ? n : n + sumTo3(n - 1);
}
console.log(sumTo3(100)); // 5050

// 4. 등차수열 합공식
function sumTo4(n) {
  return (n * (n + 1)) / 2;
}
console.log(sumTo4(100)); // 5050

2. 팩토리얼 계산하기

https://ko.javascript.info/task/factorial

function factorial(n) {
  return n == 1 ? n : n * factorial(n - 1);
}
const n = 5;
console.log("factorial(" + n + ") : " + factorial(n)); // factorial(5) : 120

3. 피보나치

// 1. 반복문(1)
function fib1(n) {
  if (n < 1) return;
  if (n == 1 || n == 2) return 1;
  const arr = [1, 1];
  for (let i = 2; i < n; i++) {
    arr.push(arr[i - 2] + arr[i - 1]);
  }
  // console.log(arr);
  return arr[arr.length - 1];
}
console.log(fib1(5)); // 5

// 2. 반복문(2)
function fib2(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}
console.log(fib2(5)); // 5

// 3. 재귀
function fib3(n) {
  return n <= 1 ? n : fib3(n - 1) + fib3(n - 2);
}
console.log(fib3(5)); // 5

재귀함수를 이용한 경우 n이 높을 때 비효율이 발생할 수 있음.
fib(3)은 fib(5)와 fib(4)를 계산할 때 모두 필요하며, 완전 다른 곳에서 독립적으로 호출되고 평가 되면서 서브호출이 늘어나고 속도가 느려짐.

4. 단일 연결 리스트 출력하기

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null,
      },
    },
  },
};

// 1. 반복
function printList1(list) {
  let tmp = list;
  while (tmp) {
    console.log(tmp.value);
    tmp = tmp.next;
  }
}

// 2. 재귀
function printList2(list) {
  console.log(list.value);
  if (list.next) {
    printList2(list.next);
  }
}