12월 31일 복기

재귀 함수를 한다 나는 다음의 나로 수렴한다.

계속 나는 내가 된다 나는 증식한다..

학습목표

재귀적으로 사고하는 법

잘게 쪼개어 사고하는 법
재귀적 사고
함수 자신의 재귀적호출
탈출 조건
재귀함수의 활용 (트리 구조)

트리 구조에 재귀 함수를 활용
JSON 구조에 재귀 함수를 활용
DOM 구조에 재귀 함수를 활용

// 이거 알게 되었는지 이따가 체크

Achievement Goals
Lesson - 재귀 함수
재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
재귀를 언제 사용해야 하는지 알고 있다.
재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.

이건 무슨 소린인가?

자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다. 이건 무슨소리인가?

실생활에 사용 되는 유용한 Tree 구조를 알고 있다.

깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.

이건 무슨 소리인가?

정말 모르겠는 소리가 많지만 학습을 해보자.

문제. 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 `arrSum을` 작성하세요.

let i;
arrSum= arr[1] + arr[2] + ...arr[i];

function arrSum(arr) {
  
  let sum =0
  for(let i =0; i <arr.length ;i ++) {
    sum += arr[i]
  }
  return sum;
}

간단한 for문을 통한 함수

근데 이것도 역순으로 생각해보면

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);
arrSum([]) = 0;

이처럼 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 합니다. 재귀의 과정을 arrSum에 적용해보면 아래와 같습니다.

라고 정의해주셨다.

잘개잘개쪼개서 원자단위까지 쪼개서 문제를 해결한다

뭔가 쪼그라들었다가 다시 커진다!라는 느낌

이렇게 문제 풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결합니다.

arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;

arrSum(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우 = arr[0] + arrSum(arr2)
   (arr2는 arr의 첫 요소를 제외한 나머지 배열)

그러니까 오늘의 내가 어제의 나를 부르고 어제의 내가 어어제의 나를 부르고

뭔가 인셉션의 현실판같은 멀티버스가 존재할까...

02_isOdd

function isOdd(num) {
  if(num===1) {
    return true;
  }
  if(num===0) {
    return false;
  }
  if(num <0) {
    return isOdd(-num);
  }
  
  return isOdd(num-2)
}

04_fibonacci

을 재귀로 풀어야되

  newArr[i] + newArr[i+1] = newArr[i+2]

function fibonacci(num) {
  if(num===0) {
    return 0;
  }
  if(num===1) {
    return 1;
  }

  return fibonacci(num-1) + fibonacci(num-2)
}

05_ arrSum

function arrSum(arr) {
  if (arr.length===0) {
    return 0;
  }
  const newArr = arr.slice(1);
  const initVal = arr[0];
  return initVal + arrSum(newArr);
}

07_arrLength

함수 arrLength는 재귀함수의 형태로 작성합니다.
반복문(for, while) 사용은 금지됩니다.
입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
arr.length 사용은 금지됩니다.
arr.isEmpty()를 통해 배열이 비어있는지 확인할 수 있습니다.
해당 메소드는 표준 자바스크립트 내장 메소드가 아니며, 문제를 위해 새롭게 정의된 커스텀 메소드입니다. 이 문제에서만 사용하시길 바랍니다.
[ ].isEmpty() === true
[1, 2].isEmpty() === false
빈 배열의 길이는 0입니다.

function arrLength(arr) {
  if(arr.isEmpty()) {
    return 0;
  }

  const newArr = arr.slice(1);
  return 1 + arrLength(newArr)
}

08_drop

function drop(num, arr) {
  /// num의 요소가 제거된 새로운 배열을 리턴

  let newArr = arr.slice(num);
  return newArr;
}

근데 이걸 재귀로 만들어야되..

function drop(num, arr) {
  /// num의 요소가 제거된 새로운 배열을 리턴
  if(num===0) {
    return arr;
  }
  if(num > arr.length) {
    return arr;
  }

  let newArr = arr.slice(1);
  return drop(num-1,newArr)
}

09_take

function take(num, arr) {
  
  let newArr = arr.slice(0,num);
  return newArr;
}

재귀함수 만들기
어렵다 어떻게 해야하나..

function take(num, arr) {

  if(num===0 || arr.length ===0) {
    return [];
  }

  let initVal= arr[0]
  let newArr = arr.slice(1);
  return [initVal].concat(take(num-1,newArr))
}

13_findMatryoshka

러시아 인형찾기

https://mercedesbernard.com/blog/recursion-and-nesting-dolls

You’re going to start with the largest doll (line 2).
You are going to open it (line 6).
It has a child. You’re going to do the same process with the child, remembering when you come back to close it that you’re going to add one for the largest doll that you opened (line 12).
Now you open the second largest doll which also has a child inside. So you’ll repeat the process, remembering when you come back to close this doll that you’re going to add one.
And so on, until you get to the smallest doll in the center. You try to open it, but it doesn’t open. There is no child. So you start the process of counting there, returning 1 (line 10).
Then you come out of that function invocation to close its parent doll and remember that you have to add 1 when you close it, so you have 1 + 1 = 2.
Then you come out of the next function invocation to close its parent and add 1, so you have 2 + 1 = 3.
And so on, until you return the final sum of nesting dolls that were in the set.

https://stackoverflow.com/questions/48102938/lisp-rest-parameters-and-recursive-calls

15_flattenArr

function flattenArr(arr) {
  // TODO: for문을 사용해서 arr[i]에 접근하고
  let newArr =[];
  for(let i =0; i < arr.length; i++) {
    if(Array.isArray(arr[i])) {
      let recursive = flattenArr(arr[i]);
      newArr.push(...recursive)
    }
    else {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}


function pintMaxNums(...args) {
console.log(args)
}
printMaxNums(10, 30, 40);

여기서는 spread syntax가 사용되었습니다. spread syntax는 iterable 한 모든 것의 (대표적으로 문자열, 배열)
요소를 "펼쳐"주는 문법을 의미합니다.
let arr = [10, 30, 40, 20]
let value = [...arr]

arr의 모든 요소를 "펼쳐"서 newArr에 넣어주었습니다. 
하나의 값을 여러개의 요소로 펼친 것이죠.

rest parmeter와
spread syntax는 표현식은 같지만
function이 다르다.

spread syntax 는 할당할때 펴준다.

rest syntax는 인자값을 담아줄때.
배열로 담아준다.

function pintMaxNums(...args) {
console.log(args)
}
pintMaxNums(10, 30, 40)

Answer = [10,30,40];

`...args`는 rest parameter, rest syntax라고 부릅니다.
남아있는 모든 인자를 하나의 배열에 담기 때문에 이렇게 부릅니다.
pintMaxNums(10, 30, 40)
함수 pintMaxNums의 인자는 총 3개입니다. 
이 인자를 모두 함수 pintMaxNums에 전달하여 실행합니다.

function pintMaxNums(...args) {
console.log(args)
}
실행이 되면 rest parameter args는 모든 남아있는 인자를 할당받습니다. 
따로 매개변수를 뺴놓지 않았음으로
args는 배열의 형태로 모든 인자를 할당받습니다. 
그렇게 때문에 답은
[10, 30, 40] A입니다.

function pintMaxNums(num1, ...args) {
console.log(args) 
  [30,40]
}

따로 매개변수를 지정했었다면, 남은 매개변수만 배열의 형태로 rest parameter args에 할당합니다.

담아준다.

14_unpackGiftbox

  TODO: giftBox를 열어서 wish가 있다면 true 를 리턴한다. 
  for문을 사용하여서 배열에 접근
  giftbox에 입력받은 문자열이(wish) 가 있다면 true를 리턴한다.
  giftbox에 입력받은 문자열이(wish) 가 없으면 false를 리턴하고 안에 있는것을 새로 깐다.
  
  
function unpackGiftbox(giftBox, wish) {
  const result = giftBox.reduce((acc, curr) => { /// acc= giftBox[i] curr = giftBox[i+1]
    if (curr === wish) { /// 중첩되는 배열이 없는 경우// accumulator 
      return true;
    } 
    // 중첩되는 배열이 있는 경우
    else if (Array.isArray(curr)) { /// curr =giftBox[i][i]; 배열을 한번 더 들어간다.
      return unpackGiftbox(curr, wish) || acc
    } else {
      return acc;
    }
  }, false);
  return result; /// 
}


다르게 표현하면 

function unpackGiftbox(giftBox, wish) {
  const aux = function (acc, curr) {
    if(curr ===wish) {
      return true;
    } else if (Array.isArray(curr) {
      return unpackGiftbox(curr, wish) || acc
    } else {
      return acc;
    }
  };
  const newArr = giftBox.reduce(aux, false);

  return newArr;
}