๐ 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์ด ๋์์ผ ํ๋ค.
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(๐ javascript ๊ฐ๋ #9 ์ฌ๊ทํจ์ / ์ํ๊ธฐ๋ณธ์ด๋ก (1)), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@dlehdus97/javascript-๊ฐ๋ -9-์ฌ๊ทํจ์-์ํ๊ธฐ๋ณธ์ด๋ก -1์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค