Udemy - 재귀

---

백준 알고리즘을 풀 때도 가장 어렵게 느껴졌고, 잘 와닿지 않았던 알고리즘 유형이다.
재귀란 말 그대로, 다시 돌아온다는 뜻이다.
쉽게 말해, 함수가 사전에 정의된 엔드포인트에 도달할 때 까지 계속 재실행되며 반복되는 것이다.

🤔  재귀함수를 사용하는 이유

1. 정말 많이 활용되는 알고리즘 패턴이다.

   ex) JSON.parse, JSON.stringify, getElementById 등등

2. 트리나 그래프 형태의 복잡한 데이터 구조를 탐색하거나 순회해야 할 때 필요하다

---

📦  콜스택 (Call Stack)

콜스택은 LIFO(Last In, First Out) 방식을 따르며, 콜스택에 함수가 차례대로 쌓인다.
가장 위에 있는 함수부터 return값이 반환되며 종료될 때마다 스택(함수)이 지워진다.

즉, 재귀함수에서는 같은 함수가 endpoint에 닿을 때 까지 콜스택에 지속적으로 쌓인다.

---

일반적으로 발생하는 재귀에서의 문제들

1. 엔드포인트가 명시되지 않은 경우

   ⇒ 콜 스택이 오버플로우 되며 오류를 발생시킨다.

2. 실수로 재귀 함수의 입력값을 고정시킬 경우에도 위와 같은 문제점이 발생할 수 있다.

즉, 재귀함수를 활용할 때는 스택 오버플로우를 반드시 방지해야 한다.

---

헬퍼 메소드 재귀

함수 안에 또 다른 재귀함수가 존재하는 경우를 통칭한다.

function collectOddValues(arr) {
  let result = [];
  // 이와 같은 헬퍼 재귀함수가 내장되어 있다.
  function helper(helperInput) {
    // 앞부분이 계속 slice되다 보면 input의 길이가 0인 지점에 다다른다.
    if (helperInput.length === 0) {
      return;
    }
    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0]);
    }
    // 계속 배열의 앞 부분을 잘라 나가며 함수를 재귀 호출 한다.
    helper(helperInput.slice(1));
  }
  helper(arr);
  return result;
}

collectOddValues([1, 2, 3, 4, 5, 6, 7, 8, 9]);

---

일반 재귀

헬퍼 메소드 함수를 사용하지 않은, 순수한 단독 재귀함수다.

🍯  꿀팁

• 배열 사용 시 : slice와 spread operator 활용을 고려
• 문자열 사용 시 : slice, substr, substring 등을 활용
• 객체 사용 시 : Object.assign 또는 spread operator 활용

function collectOddValues(arr) {
  let newArr = [];
  // 배열의 길이가 0에 다다르면 newArr 반환하며 함수 종료
  if (arr.length === 0) {
    return newArr;
  }
  // 만약 배열 맨 앞의 요소가 홀수라면 ? -> newArr에 push
  if (arr[0] % 2 !== 0) {
    newArr.push(arr[0]);
  }
  // 앞에서 정의된 newArr와 맨 앞이 잘린 arr을 합친다.
  // newArr = [...newArr, ...collectOddValues(arr.slice(1))]
  newArr = newArr.concat(collectOddValues(arr.slice(1)));
  return newArr;
}

collectOddValues([1, 2, 3, 4, 5]);

---