재귀함수

Termination Case

재귀함수에는 반드시 조건에 따라 함수 실행을 끝내는 구문이 있어야 한다.

Call Stack

여러 함수들을 호출하는 상황에서 해당 위치를 추적하는 자바스크립트 엔진을 위한 메커니즘

현재 어떤 함수가 동작하고있는지, 그 함수 내에서 어떤 함수가 호출되는지, 다음에 어떤 함수가 호출되어야 하는지 등을 추적한다

함수 실행문은 그 함수의 return 값으로 대체된다!!

재귀와 스택

재귀 깊이

가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수는 재귀 깊이(recursion depth) 라고 합니다. pow(x, n)의 재귀 깊이는 n입니다.

재귀적 순회

재귀는 재귀적 순회(recursive traversal)를 구현할 때 사용하면 좋습니다.

let company = { // 동일한 객체(간결성을 위해 약간 압축함)
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// 급여 합계를 구해주는 함수
*function sumSalaries(department) {
  if (Array.isArray(department)) { // 첫 번째 경우
    return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
  } else { // 두 번째 경우
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구함
    }
    return sum;
  }
}*alert(sumSalaries(company)); // 7700

짧고 이해하기 쉬운 코드로 원하는 기능을 구현하였습니다. 재귀의 강력함은 여기에 있습니다. 하위 부서의 깊이와 상관없이 원하는 값을 구할 수 있게 되었네요.

아래는 호출이 어떻게 일어나는지를 나타낸 그림입니다.

그림을 보면 규칙을 쉽게 확인할 수 있습니다. 객체 {...}를 만나면 서브 호출이 만들어지는 반면, 배열 [...]을 만나면 더 이상의 서브 호출이 만들어지지 않고 결과가 바로 계산됩니다.

함수 내부에선 앞서 학습한 두 문법을 사용하고 있는 것도 눈여겨보시기 바랍니다.

• 배열과 메서드 챕터에서 학습한 메서드 arr.reduce는 배열의 합을 계산해 줍니다.
• for(val of Object.values (obj))에서 쓰인 Object.values는 프로퍼티의 값이 담긴 배열을 반환합니다.

연결 리스트

자바스크립트 자료구조 연결 리스트(Linked List)

리스트 자료구조는 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다.

리스트는 수학적으로 중복을 허용하지 않는 '집합'과 다르다.

리스트라는 자료구조는 구현방밥에 따라서 다음과 같이 크게 두가지로 나뉜다.

선형 리스트(Linear List): 배열을 기반으로 구현된 리스트(배열 리스트)

연결 리스트(Linked List): 노드의 연결로 구현된 리스트

---

배열 리스트(Array List)

배열은 가장 간단한 메모리 데이터 구조다. 거의 모든 프로그래밍 언어에서 배열은 기본으로 내장된 데이터 타입이다.

배열은 동일한 데이터 타입을 연속적으로 저장한 것이다.(물론 자바스크립트에서는 다른 타입의 데이터도 한 배열에 넣을 수 있다.)

배열 리스트의 장점

간단하고 사용하기 쉽다

데이터 참조가 쉽다. 인덱스 값 기준으로 어디든 한번에 참조가 가능하다.

배열 리스트의 단점

고정된 크기: 배열의 크기가 초기에 결정되어야 한다, 변경이 불가능하다.(자바스크립트를 제외한 대부분의 언어에서는 그렇다.)

배열의 처음이나 중간에서 원소를 넣고 빼려면 비싼 연산을 빈번하게 수행한다.

---

연결 리스트(Linked List)

연결 리스트는 일련의 원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다.

다음과 같은 특징이 있다.

• 연속되는 항목들이 포인터로 연결된다.
• 마지막 항목은 Null을 가리킨다.
• 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.
• (시스템 메모리가 허용하는 한) 필요한 만큼 길어질 수 있다.
• 메모리 공안을 낭비하지 않는다.(하지만 포인터를 위한 추가의 메모리를 필요로 한다.)

배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다.

즉 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다.

노드(Node)

연결 리스트에서 각 원소는 원소 자신과 다음 원소를 가리키는 포인터가 포함된 노드(Node)로 구성된다.

https://t1.daumcdn.net/cfile/tistory/2767B53B57E8D1460C

위 그림에서 보이듯이 '데이터를 저장할 장소'와 '다른 변수를 가리키기 위한 장소'가 구분되어 있다.

그래서 둘 이상의 Node가 연결된 상황은 아래와 같다.

https://t1.daumcdn.net/cfile/tistory/25354A3857E8D15C1C

출처:

https://boycoding.tistory.com/33

[소년코딩]

Quiz

출처 : https://ko.javascript.info/recursion

**주어진 숫자까지의 모든 숫자 더하기**

중요도: 5

숫자 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 반복문 사용하기

  function sumTo(n) {
  	let sum = 0;
  	for(i=1; i<=n; i++){
  		sum += i;
      }
  	return sum;
  }

• 재귀 사용하기(n > 1일 때 sumTo(n) = n + sumTo(n-1))

  function sumTo(n) {
    if (n == 1) return 1;
    return n + sumTo(n - 1);
  }

• 등차수열 공식 사용하기

  function sumTo(n) {
    return n * (n + 1) / 2;
  }

팩토리얼

재귀를 사용하여 n!을 계산하는 함수, factorial(n)을 만들어보세요.

function factorial(n) { 
	if(n === 1) return 1;
	return n * factorial(n-1);
}

//좀 더 간결한 코드 :
return (n != 1) ? n * factorial(n - 1) : 1;

피보나치 수

피보나치 수는 첫째와 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, Fn = Fn-1 + Fn-2라는 공식으로 표현할 수 있습니다.

처음 두 항은 1이고, 그다음 항들은 2(1+1),3(1+2),5(2+3)이므로 전체 수열은 1, 1, 2, 3, 5 , 8, 13, 21 ... 형태를 띱니다.

• 재귀 함수

  function fibonacci(n) {
  	if(n === 1 || n === 2) return 1;
  	return fibonacci(n-1) + fibonacci(n-2);
  }
  
  //더 간결한 코드 :
  function fib(n) {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2);
  }

  이렇게 하면.... 수많은 서브 호출이 일어나 콜스택이 쌓이고 CPU리소스를 많이 잡아먹게 되어 처리속도가 느려진다.

• 반복문

  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)를 만들어보세요.

반복문과 재귀를 사용한 답안을 각각 만들어봅시다.

그리고 재귀를 사용한 것과 재귀를 사용하지 않은 것 중 어떤 게 더 좋은 코드인지 생각해봅시다.