[Algorithm] 기본 수학 이론 - 점화식

점화식 (= 재귀식)

• 점화식(재귀식) 이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식
• 대표적인 점화식
  • *a : 고정된 상수 
  • 등차 수열 : 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)

 

ex) 등차 수열_재귀

javascript

닫기 줄바꿈

let result;

function recursive(s, t, number) {
​​if (number == 1)
​​​​return s;
​​​​
​​​return recursive(s, t, number - 1) + t;
}

result = recursive(3, 2, 5);
console.log(result);  // output : 11

ex) 등차 수열_for문

javascript

닫기 줄바꿈

let result;

function forloop(s, t, number) {
​​let acc = 0;
​​
​​for (let i = 1; i <= number; i++) {
​​​​if (i == 1)
​​​​​​acc += s;
​​​​else
​​​​​​acc += t;
​​​​​​
​​​​console.log(i, acc);
​​}
​​
​​return acc;
}

result = forloop(3, 2, 5);
console.log(result);

 

ex) 등비 수열_재귀

javascript

닫기 줄바꿈

let result;

function recursive(s, t, number) {
​​if (number == 1)
​​​​return s;
​​​​
​​​return recursive(s, t, number - 1) * t;
}

result = recursive(3, 2, 5);
console.log(result);  // output : 48

ex) 등비 수열_for문

javascript

닫기 줄바꿈

let result;

function forloop(s, t, number) {
​​let acc = 1;
​​
​​for (let i = 1; i <= number; i++) {
​​​​if (i == 1)
​​​​​​acc *= s;
​​​​else
​​​​​​acc *= t;
​​​​​​
​​​​console.log(i, acc);
​​}
​​
​​return acc;
}

result = forloop(3, 2, 5);
console.log(result);

 

ex) 팩토리얼

javascript

닫기 줄바꿈

let result;

function recursive(number) {
​​if (number == 1)
​​​​return number;
​​​​
​​​return recursive(number - 1) * number;
}

result = recursive(5);  // 5! => 5 x 4 x 3 x 2 x 1
console.log(result);  // output : 120

 

ex) 피보나치 수열

javascript

닫기 줄바꿈

let result;

function recursive(number) {
​​if (number == 1 || number == 0)
​​​​return number;
​​​​
​​​return recursive(number - 1) + recursive(number - 2);
}

result = recursive(5);
console.log(result);  // output : 5