재귀와 스택, 무시무시한 친구들
두 가지 사고방식
- 제곱해 주는 함수 pow다.
pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16이제 두 가지 방식으로 pow를 만들어 보자!
방법 1. for문
4 아니고 16
방법 2. 재귀적
자기 자신을 호출하고 b값, 즉 회수를 줄여간다. b가 1이 되면 실행을 종료한다.
재귀는 역시 재귀적 순회
- 모든 임직원의 급여 더하기
회사의 임직원을 객체로 표현했다. sales 부서의 John과 Alice라는 2명의 직원을 배열 요소로 나타냈다 .development 부서는 sites와 internals라는 두 개의 하위 부서가 있다. sites 부서는 미래에 siteA와 siteB로 나뉠 수도 있다. 확장성을 고려해야 한다!!
--> salary라는 키값을 기준으로 for문을 계속 돌리는면
이렇게 끔찍한 혼종이 탄생한다. 그래서 우리는 재귀적으로 생각해야 한다. for in이 매우 중복된다! 이를 재귀로 혼내줄 수 있다.
--> Array 생성자로 배열인지 확인하는 것을 까묵까묵함..
가자 재귀
-
먼저 배열은 반복 순회로 구한다. 객체의 경우 중첩 객체를 재귀로 혼내주면 된다.
-
재귀 순회로 할 경우 배열을 재귀 베이스로 한다.
와 재귀 진짜 어렵다...
--> Object.values(company)로 밸류만 뽑아낸다. 아래는 subDepth의 형
[
{ name: 'John', salary: 1000 },
{ name: 'Alice', salary: 1600 }
]
{
sites:
[
{ name: 'Peter', salary: 2000 },
{ name: 'Alex', salary: 1800 }
],
internals:
[
{ name: 'Jack', salary: 1300 }
]
}subDepth를 인자로 자신을 호출한다.
이제 데이터를 추가해도 재귀로 자동 계산이 된다!!!!
갑분 연결 리스트
- 자바스크립트 배열의 가장 큰 문제는 요소 삭제와 삽입에 비용이 많이 든다는 것이다. 이를 해결하기 위해 연결리스트를 사용하자!
연결 리스트의 요소는 객체와 아래 프로퍼티들을 조합해 정의할 수 있습니다.
요소 추가하기
이렇게 귀엽고 깜찍하게 추가할 수 있다. 배열로 치면 shift()
요소 제거하기
이렇게 간단하게 이전 요소의 next만 변경하면 된다.
연결 리스트는 언제?
-
연결 리스트는 인덱스로 접근할 수 없다!
-
그래서 순서가 있는 큐, 디큐에서 사용 가능.
문제
모든 수 더하기
- 재귀
function sumTo(n) {
if (n === 1) {
return 1;
}
return n + sumTo(n - 1);
}- 등차수열
function sumTo(n) {
return n * ( n+ 1) / 2
}
console.log(sumTo(100)); // 5050팩토리얼
피보나치
와 피보나치 친구 중학교 이후로 처음이네
연결 리스트 출력하기
반복문
-
여기서 중요한 적은 item이라는 임수 변수에 list를 담고 출력하면 바꿔치기 한 것.
-
마지막 next:null 이라서 while문이 가능하다는 것
재귀
