[Algorithm] 재귀식, 등차수열, 등비수열, 피보나치 수열

2. 점화식

1) 점화식(재귀식)

: 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식

• 대표 점화식
  • 등차 수열: F(n) = F(n - 1) + a
  • 등비 수열: F(n) = F(n - 1) * a
  • 팩토리얼: F(n) = F(n - 1) * n
  • 피보나치 수열: F(n) = F(n - 1) + F(n - 2)

2) 등차수열

✔ for문

let result;

function forloop(s, t, num) {
  let acc = 0;

  for (let i = 1; i <= num; i++) {
    if (i == 1)
      acc += s;
    else
      acc += t; // 누적

    console.log(i, acc);
  }
  return acc;
}
result = forloop(3, 2, 5);
console.log(result);

✔ 재귀함수

let result;

function recursive(s, t, num) {
  if (num == 1) return s;

  return recusive(s, t, num - 1) + t;
}
result = recursive(3, 2, 5);
console.log(result); // 11

3) 등비수열

위 등차수열의 += 을 *=로 변경하면 똑같음

4) 팩토리얼

let result;

function recursive(num) {
  if (num == 1) {
    return 1;
  }
  return recursive(num - 1) * num;
  // 5 * (4 * (3 * (2 * (1 * 1)))), num값도 같이 달라지며 return
}
result = recursive(5);
console.log(result); // 120

5) 피보나치 수열🤯

let result;

function recursive(num) {
  if (num == 1 || num == 0) {
    return num;
  } 
  return recursive(num - 1) + recursive(num - 2);
}
result = recursive(5);
console.log(result); // 5