๐Ÿ“Œ javascript ๊ฐœ๋… #9 ์žฌ๊ท€ํ•จ์ˆ˜ / ์ˆ˜ํ•™๊ธฐ๋ณธ์ด๋ก  (1)

์žฌ๊ท€ํ•จ์ˆ˜

์žฌ๊ท€ํ•จ์ˆ˜๋ž€ ?

์žฌ๊ท€ ํ•จ์ˆ˜๋Š” ํ•จ์ˆ˜ ์•ˆ์—์„œ ์ง€์‹ ์˜ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
์ด๋Ÿฌํ•œ ์žฌ๊ท€ํ•จ์ˆ˜๋Š” ํŠน์ • ์กฐ๊ฑด์ด ๋์„๋•Œ ์ž์‹ ์„ ๊ทธ๋งŒ ํ˜ธ์ถœํ•˜๊ฒŒ ํ•  ์ˆ˜ ์žˆ๋Š” exit code ๊ฐ€ ํ•„์š”ํ•˜๋ฉฐ, ์ด๊ฐ™์€ ์ข…๋ฃŒ์กฐ๊ฑด์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋ฌดํ•œ ๋ฐ˜๋ณต์ด ๋œ๋‹ค.
๋˜, ์ผ๋ฐ˜์ ์ธ ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ์ž‘์„ฑํ•œ ์ฝ”๋“œ๋Š” ๋ฐ˜๋ณต๋ฌธ์œผ๋กœ๋„ ์ž‘์„ฑ์ด ๊ฐ€๋Šฅํ•˜๋‹ค.


์žฌ๊ท€ํ•จ์ˆ˜ ๊ทธ๋ฆผ์„ค๋ช…

์ด๋Ÿฐ ์ˆœ์œผ๋กœ ํ•จ์ˆ˜๊ฐ€ ์‹คํ–‰๋œ๋‹ค.


1. basic recursive function : ๊ธฐ๋ณธ ์žฌ๊ท€ํ•จ์ˆ˜

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

์žฌ๊ท€ํ•จ์ˆ˜์˜ ์ผ๋ฐ˜์ ์ธ ํ˜•์‹์œผ๋กœ, num์ด 0์ด๋ฉด 0์ด๋ผ๋Š” ๊ฐ’์„ returnํ•ด์ฃผ๊ณ , ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด num์— recursive (num - 1) ํ•จ์ˆ˜๋ฅผ ๋”ํ•ด์ค€ ๊ฐ’์„ return ํ•œ๋‹ค.
๊ทธ๋ ‡๊ฒŒ ๋˜๋ฉด num์ด 3์ด๋ฉด 3 + 2 + 1 + 0 ์ˆœ์„œ๋กœ ๊ณ„์‚ฐ์ด ๋˜๋ฉฐ ๋งˆ์ง€๋ง‰์€ 0 ์ด๋ฏ€๋กœ return 0์„ ํ•˜๋ฉฐ ๊ณ„์‚ฐ์ด ๋๋‚˜๊ฒŒ ๋œ๋‹ค. ๋”ฐ๋ผ์„œ, ๋‹ต์€ 6


2. factorial function : ํŒฉํ† ๋ฆฌ์–ผ ํ•จ์ˆ˜

function factorial(x) {
  if (x === 0) return 1;

  return x * factorial(x - 1);
}

const num = 3;

let result = factorial(num); 

// The factorial of 3 is 6
console.log(`The factorial of ${num} is ${result}`);

ํŒฉํ† ๋ฆฌ์–ผ ํ•จ์ˆ˜๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ํŒฉํ† ๋ฆฌ์–ผ์ด๋ผ๋Š” ์ˆ˜ํ•™ ๊ฐœ๋…์„ ๋จผ์ € ์•Œ์•„์•ผ ํ•œ๋‹ค.

ํŒฉํ† ๋ฆฌ์–ผ์ด๋ž€?

ํŒฉํ† ๋ฆฌ์–ผ์€ ์ฐจ๋ก€๋Œ€๋กœ ๊ณฑํ•ด๋‚˜๊ฐ€๋Š” ์ˆ˜๋กœ ์˜ˆ๋ฅผ ๋“ค์–ด 5! ์ผ๋•Œ๋Š” 5 ~ 1๊นŒ์ง€์˜ ์ˆ˜๋ฅผ ์ „๋ถ€ ๊ณฑํ•ด์„œ 5 x 4 x 3 x 2 x 1 = 120 ์ด๋ ‡๊ฒŒ ํ’€์–ด๋‚˜๊ฐ€๋Š” ๊ฒƒ์ด๋‹ค.
์ฆ‰, n๋ถ€ํ„ฐ 1๊นŒ์ง€์˜ ์ˆ˜๋ฅผ ์ฐจ๋ก€๋กœ ๊ณฑํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

์œ„์˜ ์‹์€ 3๋ถ€ํ„ฐ 1๊นŒ์ง€์˜ ์ˆ˜๋ฅผ ๊ณฑํ•˜๋Š” factorial์ด๊ณ ,
์•„๋ž˜๋Š” ์œ„์—๋„ ์˜ˆ์‹œ๋ฅผ ๋“ค์—ˆ๋˜ 5!์˜ ์˜ˆ์‹œ ์ฝ”๋“œ์ด๋‹ค.

let result_2;

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

  return recursive(number - 1) * number;
}

result_2 = recursive(5); // 5! = 5 * 4 * 3 * 2 * 1
console.log(result_2);
// 120 ์ด ๋‚˜์˜จ๋‹ค.

์šฐ์„  recursive๋ผ๋Š” ํ•จ์ˆ˜์—์„œ number๊ฐ€ 1์ด๋ฉด number๋ฅผ return ํ•ด์ค€๋‹ค.
์—ฌ๊ธฐ์„œ ํŒฉํ† ๋ฆฌ์–ผ์€ ๊ณฑํ•ด๋‚˜๊ฐ€๋Š” ํ•จ์ˆ˜์ด๋ฏ€๋กœ ์ดˆ๊ธฐํ™” ๊ฐ’์ด 1์ด ๋˜์–ด์•ผ๋งŒ ํ•œ๋‹ค.
number๊ฐ€ 1์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” recursive ํ•จ์ˆ˜๋ฅผ ๋‹ค์‹œ ํ˜ธ์ถœํ•ด number์—์„œ -1ํ•œ ์ˆ˜๋ฅผ ์ด์ „ number์— ๊ณฑํ•ด์ค€ ๊ฒƒ์„ return ํ•ด์ค€๋‹ค.

๊ทธ๋ ‡๊ฒŒ ๋˜๋ฉด recursive(5) = 5 x 4 x 3 x 2 x 1 ์ด ๋˜๋ฉฐ, 120์ด ๋‚˜์˜จ๋‹ค.


3. AP function : ๋“ฑ์ฐจ์ˆ˜์—ด

๋“ฑ์ฐจ์ˆ˜์—ด์€ forloop๊ณผ ์žฌ๊ท€ํ•จ์ˆ˜ ๋‘๊ฐ€์ง€์˜ ๋ฐฉ๋ฒ•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋Š”๋ฐ ์šฐ์„  ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ๋‹ค๋ฃจ๋Š” ๋ฐฉ๋ฒ•์€

let Result;

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

// [ ๋“ฑ์ฐจ์ˆ˜์—ด์˜ ๋™์ž‘์›๋ฆฌ ]
// number : 5 , recursive(s, t, 4) => 9 + 2 = 11
// number : 4 , recursive(s, t, 3) => 7 + 2 = 9
// number : 3 , recursive(s, t, 2) => 5 + 2 = 7
// number : 2 , recursive(s, t, 1) => 3 + 2 = 5
// number : 1 ==> 3 => ๊ทธ๋ƒฅ s๊ฐ’์œผ๋กœ ์ง€์ •๋œ 3์„ ๋‚ด๋ณด๋ƒ„

Result = recursive(3, 2, 5);
console.log(Result);
//  ๋”ฐ๋ผ์„œ, 11 ์ด ๋‚˜์˜ด.

๋“ฑ์ฐจ์ˆ˜์—ด์ด๋ž€?

๋“ฑ์ฐจ์ˆ˜์—ด์€ ์—ฐ์†ํ•˜๋Š” ๋‘ํ•ญ์˜ ์ฐจ์ด๊ฐ€ ์ผ์ •ํ•œ ์ˆ˜์—ด์ด๋ฉฐ ์ฆ‰, ๊ฐ™์€ ๊ฐ„๊ฒฉ(๊ณต์ฐจ)์„ ๋‘๊ณ ๋ฒŒ์–ด์ ธ ์žˆ๋Š” ์ˆ˜๋ฅผ ์˜๋ฏธํ•œ๋‹ค.
์˜ˆ) 1, 3, 5, 7, 9 ... --> ๊ณต์ฐจ๋Š” 2 (๊ณตํ†ต์˜ ๊ฐ„๊ฒฉ 2)

result๋ผ๋Š” ๋นˆ ๋ณ€์ˆ˜๋ฅผ ์šฐ์„  ์„ ์–ธํ•ด์ฃผ๊ณ ,
recursive์— s, t, number๋ผ๋Š” ๊ฐ’์„ ์ €์žฅํ•ด์ค€๋‹ค.
๋งŒ์•ฝ์— number๊ฐ€ 1์ด๋ผ๋ฉด s๋ฅผ return ํ•ด์ค€๋‹ค.
--> ์ด๊ฒƒ์ด exit code์™€ ๊ฐ™๊ธฐ ๋•Œ๋ฌธ์— break point๋ผ๊ณ  ์ฃผ์„์„ ๋‹ฌ์•„์ฃผ์—ˆ๋‹ค.

๋งŒ์•ฝ number๊ฐ€ 1์ด ์•„๋‹ˆ๋ผ๋ฉด recursive์— s, t, number - 1์„ ๋‹ด์€ ๊ฐ’์— -t๋ฅผ ํ•ด์ค€ ๊ฐ’์„ return ํ•œ๋‹ค. ๋‚˜๋จธ์ง€๋Š” ์ฃผ์„ ์ฐธ๊ณ .


4. geometric sequence function : ๋“ฑ๋น„์ˆ˜์—ด

๋“ฑ๋น„์ˆ˜์—ด๋„ ๋“ฑ์ฐจ์ˆ˜์—ด๊ณผ ๋น„์Šทํ•˜๊ฒŒ foorloop๊ณผ ์žฌ๊ท€ํ•จ์ˆ˜ ๋ชจ๋‘ ๊ตฌํ˜„๊ฐ€๋Šฅํ•˜๋‹ค.
์šฐ์„  ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์€

let Result_1;

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

  return recursive(s, t, number - 1) * t;
}

// [ ๋“ฑ๋น„์ˆ˜์—ด์˜ ๋™์ž‘์›๋ฆฌ ]
// number : 5 recursive(s, t, 4) * t => 24 * 2 = 48
// number : 4 recursive(s, t, 3) * t => 12 * 2 = 24
// number : 3 recursive(s, t, 2) * t => 6 * 2 = 12
// number : 2 recursive(s, t, 1) * t => 3 * 2 = 6
// number : 1 ==> 3 => ์ง€์ •๋œ s๊ฐ’์ด 3 ์ด๋ฏ€๋กœ

Result_1 = recursive(3, 2, 5);
console.log(Result_1);
// 48 ์ด ๋‚˜์˜จ๋‹ค.

๋“ฑ์ฐจ์ˆ˜์—ด์ด๋ž€ ?

๋“ฑ์ฐจ์ˆ˜์—ด์ด๋ž€ ๊ฐ ํ•ญ์ด ์ฒซ๋ฒˆ์งธ ํ•ญ๊ณผ ์ผ์ •ํ•œ ๋น„์œจ์„ ๊ฐ–๋Š” ์ˆ˜์—ด์ด๋ฉฐ ์‰ฝ๊ฐœ ๋งํ•˜์ž๋ฉด, ๊ฐ™์€ ๋น„์œจ(๊ณต๋น„)์„ ๊ฐ€์ง€๊ณ  ๋–จ์–ด์ ธ์žˆ๋Š” ์ˆ˜๋ฅผ ๋งํ•œ๋‹ค.
์˜ˆ) 1, 2, 4, 8, 16, 32 ... --> ๊ณต๋น„๋Š” 2

๋“ฑ๋น„์ˆ˜์—ด์„ ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ๋‚˜ํƒ€๋‚ด๋Š” ๊ฒƒ์€ ๋“ฑ์ฐจ์ˆ˜์—ด๊ณผ ๊ฑฐ์˜ ์œ ์‚ฌํ•˜๋ฉฐ, ๊ธฐํ˜ธ๋งŒ * ์„ ์จ์ฃผ๋ฉด ๋œ๋‹ค. ์ž์„ธํ•œ ๊ฑด ์ฝ”๋“œ ์ฐธ์กฐ.


5. fibonacci numbers : ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด

ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์ด๋ž€ ?

์ฒซ์งธ ๋ฐ ๋‘˜์งธํ•ญ์€ ๊ฐ™์œผ๋ฉฐ, ๊ทธ ๋‹ค์Œํ•ญ์€ ๋ฐ”๋กœ ์•ž ๋‘ ํ•ญ์˜ ๋”ํ•œ ๊ฐ’์ธ ์ˆ˜์—ด์ด๋‹ค.
์ฆ‰ ์ฒซ์งธํ•ญ์ด 1์ด๋ผ๋Š” ๊ฐ€์ •ํ•˜์— 1, 1, 2, 3, 5, 8, 13 ... ์ˆœ์œผ๋กœ ์ด์–ด์ง€๋Š” ์ˆ˜์—ด์ด๋‹ค.
์‹์œผ๋กœ ํ‘œํ˜„ํ•˜๋ฉด f(n) = f(n-1) + f(n-2)

let Result_2;

function recursive(number) {
  if (number == 1 || number == 0) {
    return number;
  }

  // f(n) = f(n-1) + f(n-2)
  return recursive(number - 1) + recursive(number - 2);
}

// [ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์˜ ๋™์ž‘์›๋ฆฌ ]
// number : 5 -> f(4) + f(3) ==> 3 + 2 = 5
// number : 4 -> f(3) + f(2) ==> 2 + 1 = 3
// number : 3 -> f(2) + f(1) ==> 1 + 1 = 2
// number : 2 -> f(1) + f(0) ==> 1 + 0 = 1
// number : 1 ==> 1



Result_2 = recursive(5);
console.log(Result_2);
// 5 ๊ฐ€ ๋‚˜์˜จ๋‹ค.

result_2 ๋ผ๋Š” ๋นˆ ๋ณ€์ˆ˜๋ฅผ ๋จผ์ € ์„ ์–ธํ•ด์ค€๋‹ค.
๋งŒ์•ฝ์— number๊ฐ€ 1์ด๊ฑฐ๋‚˜ 0 ์ผ๋•Œ, number๋ฅผ return ํ•ด์ค€๋‹ค. ( ์—ฌ๊ธฐ์„œ || ๋Š” or ์—ฐ์‚ฐ์ž -> '๋˜๋Š”' ์œผ๋กœ ํ•ด์„ ) ๊ทธ ์ด์™ธ์˜ ๊ฒฝ์šฐ ์ผ๋•Œ๋Š” recursive(number - 1) ์„ ํ•œ ๊ฐ’๊ณผ recursive(number - 2)๋ฅผ ํ•œ ๊ฐ’์„ ๋”ํ•ด์ค˜์„œ return ํ•ด์ค€๋‹ค.

์ฆ‰ number๊ฐ€ 2๋ผ๋ฉด, recursive(1)๊ณผ recursive(0) ์ผ๋•Œ๋ฅผ ๋”ํ•ด์„œ 1, 0 ์„ ๋”ํ•œ ๊ฐ’์ธ 1์ด ๋‚˜์™€์•ผ ํ•œ๋‹ค.

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ