[TIL: 6주차] 재귀함수

28523 단어 JavaScriptJavaScript

재귀함수

재귀함수를 쓸 줄 알아야 프로그래머스 레벨 2 정도 수준이라는데, 나한텐 개념 이해가 어려워도 너무 어려웠다. 다른 개념들은 다양한 채널에서 강의를 선택해서 골라 들을 수 있었는데, 재귀함수는 이상하게 유튜브 강의를 아무리 찾아봐도 모든 채널이 팩토리얼과 총합, 피보나치 수열 예제만 반복 반복 반복…
5*4*3*2*1 이거 하나하나 안 보여줘도 그게 이해가 안 되는 게 아니라ㅠㅠ 응용이 어려운건데……🥲💦💦💦

팩토리얼 함수만 아무리 쳐다봐도 응용이 어려운 나 같은 사람을 위해, 며칠간 내가 재귀함수만 쳐다보면서 이 개념을 이해하기 위해 어떤 방식으로 접근했는지 설명해보려고 한다.

재귀함수 이해하기

재귀함수를 이해하기 위해선 이 점을 기억해야 한다.

재귀함수는 모두 반복문으로 변환할 수 있다!

개념적으로 그렇기도 하지만, 달리 보면 반복문의 처리과정을 이해하고 있으니 재귀함수도 금방 개념을 몸에 익힐 수 있다는 말이다! 😠🔥
반복문도 처음엔 코드 치기 막막하고 어려웠다는 걸 떠올려 보자…

팩토리얼을 구하는 함수를 예로 들어보자.
(팩토리얼 예제 지겹다고 하고 저도 이 예제를 써서 죄송합니다…)

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

팩토리얼 함수는 많은 자료들이 이렇게 쓰는 것을 제안하고 있을 것이다.
하지만 재귀함수를 처음 배우는 나한텐 이 문법이? 이해가? 가지? 않는다?
return은 함수를 종료하는 것 아닌가? 전달인자로 n-1이 입력된다고 생각하면?

머리가 복잡해진다…

일단 이걸 반복문으로 써보자.

function factorial(n){
  let result = 1;
  
  for(let i = 1; i <= n; i++){
    result = result * i;
  }
  
  return result;
}

보통 이런 코드를 쓸 것이다.

함수는 1*2*…*(n-1)*n 이런 오름차순으로 실행될 것이고.

이 같은 반복문을 증감식만 뺄셈으로 바꿔준다고 생각하면 재귀함수에 다가가기 한결 편해진다.

function factorial(n){
  let result = 1;
  
  for(let i = n; i <= 1; i--){
    result = result * i;
  }
  
  return result;
}

위와 같은 코드지만, 반복문 실행 조건만 i가 n에서 시작해 1이 될 때까지 i를 하나씩 빼주는 조건으로 변경해줬다.

이 코드는 n*(n-1)*…*2*1 이렇게 내림차순으로 실행될 것이다.

그렇다면 다시 재귀함수로 돌아가보자.
재귀함수는 이런 문법으로 작성된다.

function recursiveFunction(parm){
  if(base case: 반복문의 조건식){
    return value;
  } else {
    return recursiveFunction(parm의 변화값: 반복문의 증감값);
  }

for문에서 조건식이 false가 될 때 조건문을 종료하듯, 기본 케이스(base case)에 저 조건문을 써준다고 생각하면 된다. 그래서 다들 베이스 케이스를 탈출 조건이라고 부른다.

그리고 보통 간단한 예제에서는 재귀 케이스(recursive case)가 되는 else를 자주 생략하고 작성할 뿐이다.

다시 재귀함수의 기본 개념을 생각해 보자.

재귀함수는 자기 자신을 호출하는 함수를 말한다.

위 코드를 다시 자세히 보면, 베이스 케이스에서는 '값'을 리턴하고 리커시브 케이스에서는 '함수'를 호출하고 있다. 그래서 베이스 케이스가 없다면, 함수는 영원히 함수를 호출하는 루프에 빠지게 될 것이다. 그래서 이 루프를 탈출하기 위해 가장 작은 단위의 함수는 베이스 케이스로 진입해 함수가 아닌 '값'을 리턴해야 하는 것이다.

재귀함수는 이런 초과부등호(>) 같은 구조를 상상하면 된다.

function factorial(n){
  function factorial(n-1){
    ...
      function factorial(2){
        function factorial(1){
          return 1;
        }
        return 1*2;
      }
    return 1*2*…*(n-1);
  }
  return 1*2*…*(n-1)*n;
}

개인적으론 리턴 = 함수 종료처럼 느껴져서 재귀함수 이해가 어려웠는데,

1) 가장 작은 단위의 함수가 실행하는 베이스 케이스(이 경우에는 facotorial(1))가 1이라는 값을 반환하고 종료되면,
2) facotrial(2)가 factorial(1)이라는 함수를 1이라는 값으로 받아들여, 새롭게 n으로 할당된 2를 곱해 2를 반환하고,
…

이 과정이 반복되다가 factorial(n-1)에서 1*2*…*(n-1)이 반환되고 함수가 종료되면, 맨 마지막 함수인 factorial(n)이 초기값인 전달인자 n을 마지막으로 곱해 값으로 반환하고 종료되는 것이다.

즉, 베이스 케이스가 반환한 값을 받아 다음 함수가 계산을 하고 차례차례 값이 반환시킬 때까지 나머지 함수는 앞 함수의 처리를 기다리는 상태가 된다. 이 과정에서 처리를 기다리는 함수들은 '실행 컨텍스트 스택'에 쌓이기 때문에 재귀함수는 수행 속도를 떨어뜨리고, 여분의 기억 공간을 소모하는 비효율적인 코드가 될 수도 있으니 코드 작성 시 주의가 필요하다.

다시 팩토리얼 예제로 돌아가 보면,

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

factorial(3)을 실행한다고 가정해보자.

  1. 전달인자 3은 1보다 커서 베이스 케이스를 지나치기 때문에, factorial(3)은 3xfactorial(2)를 반환한다.
  2. factoiral(2)는 2xfactorial(1)을 반환한다.
  3. factorial(1)은 베이스 케이스의 조건에 부합하여, 1이라는 '숫자'를 반환한다.
  4. 나머지 더 큰 단위의 함수들은 함수를 값으로 변환하여 실행된다.

이렇게 베이스 케이스는 값을 반환한다는 단순한 조건만 기억하면, 이제 재귀함수를 배열, 객체, DOM에도 응용할 수 있다.

예제

기본 개념을 이해했다면 배열과 객체, DOM에서 재귀함수를 어떻게 활용하는지 확인해보자.

1) 배열에서 재귀함수의 활용

  1. 배열과 숫자를 입력받아, 배열 앞에서부터 num개의 요소가 제거된 새로운 배열을 리턴한다.
function drop(num, arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(num >= arr.length){
    return [];
  } else if(num === 0){
    return arr;
  }

  let tail = arr.slice(1);

  return drop(num-1, tail);
}

베이스 케이스에서 배열로 된 전달인자 arr, 즉 값을 반환하고 있는 것을 확인할 수 있다.

  1. 배열과 숫자를 입력받아, 배열 앞에서부터 num개의 요소만 포함된 새로운 배열을 리턴한다.
function take(num, arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(num === 0 || arr.length === 0){
    return [];
  }

  let head = arr[0];
  let tail = arr.slice(1);

  return [head, ...take(num-1, tail)];
}

위와 유사해 보이는 문제지만 접근법이 조금 다르다.
베이스 케이스는 빈 배열을 반환하고 있으며, 재귀함수는 배열 내부에서 호출된다.

2) 객체에서 재귀함수의 활용

  • 마트료시카에 대한 정보를 담은 객체와 숫자(size)를 입력받아 조건에 맞는 사이즈의 인형이 있는지 여부를 리턴한다.
    • 인자는 'matryoshka', 'size' 속성을 갖는 재귀적으로 정의된 객체
    • matryoshka.matryoshka는 null 또는 matryoshka 객체
    • matryoshka.size는 중첩될수록 1씩 작아진다.
function findMatryoshka(matryoshka, size) {
  // TODO: 여기에 코드를 작성합니다.
  if(matryoshka === null || Object.keys(matryoshka).length === 0){
    return false;
  }

  if(matryoshka.size === size){
    return true;
  }

  return findMatryoshka(matryoshka.matryoshka, size);
}

불리언을 반환하고 있기 때문에 베이스 케이스를 좀 더 단순하게 생각할 수 있다.
리커시브 케이스의 전달인자는 객체를 값으로 가진 객체의 키가 되며, 이를 응용하면 2차원 배열에 접근하는 방법도 금방 떠올릴 수 있을 것이다.

3) DOM에서 재귀함수의 활용

  • 재귀함수로 menu 객체의 트리 구조 구현하기

const root = document.getElementById('root');
function createTreeView(menu, currentNode) {
  // TODO: createTreeView 함수를 작성하세요.

  for(let i = 0; i < menu.length; i++){ 
    const li = document.createElement("li");
    const ul = document.createElement("ul");
    const input = document.createElement("input");
    const span = document.createElement("span");

    if(menu[i].children === undefined){
      currentNode.append(li);
      li.textContent = `${menu[i].name}`;
    } else {
      currentNode.append(li);
      li.append(input, span, ul);
      input.setAttribute("type", "checkbox");
      span.textContent = `${menu[i].name}`;

      createTreeView(menu[i].children, ul);
    }
  }
}

createTreeView(menu, root);

베이스 케이스는 menu 객체에 children 키가 없을 때 실행되며,
children이 있을 땐 인자가 가진 children 키의 값과 현재 노드의 자식 노드인 ul을 인자로 전달한다.

나는 아직도 createElement가 생성자로만 보여서…
반환값을 전달한다는 생각을 못하고, 처음에는 두 번째 전달인자를 querySelectorAll(currentNode > li) 이렇게도 써보고 currentNode.children[i] 저렇게도 써보면서 별 코드를 다 적어봤는데… 의외로 간단하게 풀렸다.

currentNode.children[i]는 children이 배열로 출력되길래 대충 인덱스를 넣어본 건데, currentNode의 자식 요소를 찾으면 root의 li로 들어가게 되니 콜드 브루가 음료 상위로 들어가고… 난리였음……

역시 DOM은 아직 어렵다…… 🤯

해결!

아무튼 나는 이렇게 재귀함수의 개념을 잡았는데 혹시 같은 부분에서 헤매고 있던 분들이 있다면 이 글이 도움이 되었으면 좋겠다.

예전에 나는 반복문으로 피보나치 수열로 된 배열을 만들 때 이런 코드를 짠 적이 있다.

function fibonacci(num) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [0, 1];

  for(i = 0; i <= num; i++){
    if(num === 0){
      result.pop();
      break;
    } else if (num === 1){
      break;
    } else {
      result.push(result[i] + result[i+1]);
      result = result.slice(0, num+1);
    }
  }

  return result;
}

result에 i-2번째 인덱스와, i-1번째 인덱스를 더한 값을 추가하는 코드였다면, 즉 뺄셈으로 사고하면 단순해질 코드를 나는 항상 덧셈을 기본으로 사고해서 코드를 복잡하게 만드는 경향이 있었다. 그리고 그게 재귀함수에 와서 드디어 터진 것 같다…

이제 막 프론트엔드 과정 시작인데 벌써 막혀서… 앞으로가 걱정이다 🥲

추천 유튜브

[Web Dev Simplified] What Is Recursion - In Depth
https://www.youtube.com/watch?v=6oDQaB2one8

Chaos Destuction #2 - 간단한 테스트
[스파르타 웹개발 종합반] 4주차 정리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage