22.11.26 토
DAY 13 - javascript (기초다지기)
📌재귀와 스택
재귀(recursion) : 함수가 자기 자신을 호출 하는 경우
📖 풀어보기
✏️ 주어진 숫자까지의 모든 숫자 더하기
숫자 1 + 2 + ... + n을 계산하는 함수 sumTo (n)을 만들어보세요.
예시:
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050아래 방법을 사용해 세 가지 답안을 만들어보세요.
- for 반복문 사용하기
- 재귀 사용하기(n > 1일 때 sumTo(n) = n + sumTo(n-1))
- 등차수열 공식 사용하기
예시 :
function sumTo(n) { /*... 답안은 여기에 작성 ... */ }
alert( sumTo(100) ); // 5050➡️ for 반복문 사용하기
function sumTo(n) {
let sum = 0;
for (let i = 1; i < n + 1; i++) {
sum += i;
}
return sum;
}
➡️ 재귀 사용하기
function sumTo(n) {
if (n > 1) {
return n + sumTo(n - 1);
} else {
return n;
}
}➡️ 등차수열 공식 사용하기
function sumTo(n) {
let sum = (n * (n + 1)) / 2;
return sum;
}등차수열은 잘 모르겠어서, 등차수열 설명해주는곳에 있는 공식을 썼더니 결과값이 비슷하는 나왔다.
for를 가장 많이 사용하고, 재귀를 사용해본 적이 없는거 같다.
그치만 재귀를 사용하는 방법이 속도가 더 느리다.
✏️ 팩토리얼 계산하기
팩토리얼(factorial)은 n이 자연수일 때, 1부터 n까지의 모든 자연수의 곱을 의미합니다. n 팩토리얼은 n!으로 표시합니다.
팩토리얼은 아래와 같이 정의할 수도 있습니다.
n! = n * (n - 1) * (n - 2) * ...*1자연수 n에 대한 n 팩토리얼
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120재귀를 사용하여 n!을 계산하는 함수, factorial(n)을 만들어보세요.
alert( factorial(5) ); // 120힌트: n!은 n (n-1)!입니다. 3! = 3 2! = 3 2 1! = 6같이 말이죠.
➡️
function factorial(n) {
return n ? n * factorial(n - 1) : 1;
}
alert( factorial(5) ); // 120✏️ 피보나치 수 계산하기
피보나치 수는 첫째와 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, Fn = Fn-1 + Fn-2라는 공식으로 표현할 수 있습니다.
처음 두 항은 1이고, 그다음 항들은 2(1+1),3(1+2),5(2+3)이므로 전체 수열은 1, 1, 2, 3, 5 , 8, 13, 21 ... 형태를 띱니다.
피보나치 수는 황금 비율 등 우리 주변을 둘러싼 수많은 자연 현상과 관련이 있습니다.
n 번째 피보나치 수를 반환하는 함수 fib(n)을 작성해보세요.
예시:
function fib(n) { /* 답안은 여기에 작성 */ }
alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
➡️주의: fib (77)를 호출했을 때 연산 시간이 1초 이상 되면 안 됩니다.
- 재귀를 이용한 정답
function fib(n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}
fib(77)
// 위에 함수를 실행하면, 시간이 너무 오래걸린다. - 반복문을 이용한 정답
function fib(n) {
let a = 1;
let b = 1;
for (let i = 3; i <= n; i++) {
let c = a + b;
a = b;
b = c;
}
return b;
}반복문을 사용하면, 연산속도가 빠르고 중복되는 계산이 없다는 장점이 있다.
✏️ 단일 연결 리스트 출력하기
재귀와 스택에서 설명한 바 있는, 단일 연결 리스트(single-linked list)가 있다고 가정해 봅시다.
let list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};리스트 내 항목을 차례대로 하나씩 출력해주는 함수 printList(list)를 만들어보세요.
반복문과 재귀를 사용한 답안을 각각 만들어봅시다.
그리고 재귀를 사용한 것과 재귀를 사용하지 않은 것 중 어떤 게 더 좋은 코드인지 생각해봅시다.
➡️ 반복문을 사용한 해답
let list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
function printList(list) {
let tmp = list;
while (tmp) {
alert(tmp.value);
tmp = tmp.next;
}
}
printList(list);list를 tmp에 저장 후, list의 value를 출력한 뒤에 다시 tmp에 tmp.next를 저장해 tmp를 출력한다.
여기서 tmp.next가 존재하지 않을때까지 반복해 출력한다.
➡️ 재귀를 사용한 해답
let list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
function printList(list) {
alert(list.value); // 현재 요소를 출력합니다.
if (list.next) {
printList(list.next); // 같은 방법을 사용해 나머지 요소를 출력합니다.
}
}
printList(list);list를 출력한뒤,
list.next가 존재하면 다시 함수를 실행시켜 출력한다.
답안을 보면, 해석은 가능한데 막상 내가 함수를 만드려면 어떻게 해야할 지 모르고 있다.
💬 오늘의 느낀점
일단 재귀가 어떤 의미인지는 알겠지만, 실 사용을 잘못하겠다.
쉽지 않은 느낌 어렵다ㅜㅜ
