Recursion

• 숫자 배열의 모든 숫자를 프린트합니다. 여기에서 반드시 재귀를 사용해야 합니다.

const printArray = function () {
  // TODO
};

1. 뭐가 문제였나?

ㅈ...재귀!! 분명히 [1,2,[3,4,[[5]],,6,]7] 이런 배열이 테스트케이스로 들어올테니, 인덱스가 배열이면 그 배열을 재귀돌리고 배열이 아니면 숫자를 출력 후 재귀, 공통적으로 재귀돌릴 때 인자는 0번째 인덱스를 뺀 나머지 배열, 종료조건은 재귀들어온 배열의 길이가 0일 때.

재귀는 아 이렇게 짜면 되지 않을까~ 생각하는 것 까지는 머리 쥐어짜내면 어떻게 하겠는데, 막상 짜놓고 보면 내가 생각했던거랑 다르게 동작할 때가 많고, 거기서 고쳐보겠다고 여기저기 손대다 보면 나중엔 이상한 혼종이 되어있는 경우가 많다. 어, 이거 산으로 간다 싶으면 과감하게 싹 날리고 처음부터 다시 짜보는게 차라리 나을때가 많다.

2. 어떻게 풀어냈나?

const printArray = function (array) {
  
  function _print(targetArr) {

    // 종료조건 : 인자 배열의 길이가 0인 경우
    if (targetArr.length === 0) {
      return;
      
    } else {
      // 인자배열의 0번째 인덱스를 볼거다.
      let temp = targetArr[0];
      
      // 0번째 인덱스가 배열이면 해당 인덱스를 재귀, 그 인덱스 뺀 나머지 배열 재귀
      if (Array.isArray(temp)) {
        _print(temp);
        _print(targetArr.slice(1));
        
      // 0번째 인덱스가 배열 아니면 콘솔에 찍고 그 인덱스 뺀 나머지 배열 재귀
      } else if (temp) {
        console.log(temp);
        _print(targetArr.slice(1));
        
      // 0번째 인덱스가 비어있는 경우, 그 인덱스 뺀 나머지 배열 재귀
      } else {
        _print(targetArr.slice(1));
      }
    }
  }

  _print(array);
};

다 짜여있는 코드를 보면 아~ 이렇게~ 하고 납득이 되는데 내가 짜려고 하면 잘 안 된다. 그나마 위안은 그래도 이제 납득은 된다는 점이다. 이 코드같은 경우는 며칠간 매일 좀 또 짜보고 또 짜보고 하면서 재귀랑 친해져야 할 것 같다.

---

Tree-map

• Tree 클래스에 addChild 및 map 메소드를 구현하세요.
  map 메소드는 함수를 인자로 받습니다.
  이는 트리를 가로질러 각 노드의 값을 매핑 함수에 전달하고, 그 결과를 포함하는 새 트리를 생성합니다.
  따라서, map 메소드는 Tree와 구조와 같고, 값이 다른 트리를 반환합니다.
  그러나, map 메소드를 사용하는 원래 트리는 수정되어서는 안됩니다.

const Tree = function (data) {
  this.data = data;
  this.children = [];
};

Tree.prototype.addChild = function(child) {
  // your code here
};

Tree.prototype.map = function(callback) {
  // your code here
};

1. 무엇이 문제였나?

add는 새 트리 하나 만들어서 this 의 children 에다가 push하면 되니까 ok. 그런데 map 의 경우에는 노드들에 callback만 적용하면 되는게 아니라 새 트리를 반환해야 한다니 머리위에 물음표가 찍히기 시작했다. 트리 순회하는건 그렇다 쳐도 새 트리를 어떻게 만들라는거지?

2. 어떻게 풀어냈나?

const Tree = function (data) {
  this.data = data;
  this.children = [];
};

Tree.prototype.addChild = function(child) {
  
  const node = new Tree(child);
  this.children.push(node);
  return this
};

Tree.prototype.map = function(callback) {
  const newTree = new Tree();
  newTree.data = callback(this.data);
  newTree.children = this.children.map(function(child) {
    return child.map(callback)
  });
  return newTree;
}

• map 함수가 돌아가는 원리

1. 새 트리를 하나 만들고, 그 트리의 data에 기존 data에 callback을 적용한 결과를 할당한다.
2. 기존 트리의 children배열 요소들을 순회하면서 각각의 요소에 callback을 인자로 넣어 재귀돌린다.
3. 그러면 children의 children에 다시 재귀가 들어가고, 재귀된 children의 children에 다시 재귀가 돌아가고... 하면서 스택이 쌓인 뒤, 해소되는 과정에서 문제가 요구한 새 트리가 만들어지고 마지막에 리턴되면서 함수가 종료된다.