JAVASCRIPT - 2022. 1. 18.

재귀함수 뽀개기 javascript

🙏재귀함수 뽀개기 javascript

안녕하세요 TriplexLab 입니다.
오늘은 재귀함수[재귀패턴]에 관해서 이야기를 해보도록 하겠습니다.

👉재귀함수 개념 (재귀패턴)

재귀적으로 문제를 풀기 위해서는 문제를 같은 형태의 더 작은 문제로 쪼개야 하기 때문에 패턴을 찾아야 합니다.
재귀함수를 쓸 때는 항상 두 경우가 있어야 합니다.
base case: 더 이상 문제를 쪼갤 필요가 없는 종료된 경우
recursive case: 문제를 쪼개서 풀어가는 경우

아주 간단한 예시를 살펴 봅시다.🙏

function f(n) {
    if (n <= 1) { // base case
       return 1 
    }
    return n + f(n-1) // recursive case
}
console.log(f(4)) //결과값 10

// 재귀패턴 순서 설명
// return    최종
//4 + f(3)   4 + 3 + 2 + 1
//3 + f(2)   3 + 2 + 1
//2 + f(1)   2 + 1
//1 + f(1)   1 (base case에 걸린 경우)

또 다른 예시🔥
재귀 함수 (Recursion)은 자기 자신을 호출하는 함수 입니다.
간단한 예시로 정수 n부터 1까지 출력하는 countdown 함수를 봅시다.
countdown함수 내에서 또 countdown함수를 호출했습니다.

function countdown(n){
    if(n > 0){ // base case
        console.log(n)
        return countdown(n - 1) // recursive case
    }
}
countdown(4)

실행하면 실제로 4,3,2,1이 출력됩니다. 어떻게 된걸 까요?
왼쪽 8번줄에서 countdown함수가 호출되고, 파리미터 n으로 정수 4가 넘어갔습니다.
4는 0보다 크기 때문에 콘솔에 4가 출력되고 그리고 countdown 3이 불립니다.
3도 0보다 크기 때문에 콘솔에 3이 출력되고 countdown 2가 호출됩니다.
2도 0보다 크기 때문에 콘솔에 2이 출력되고 countdown 1이 호출됩니다.
1도 0보다 크기 때문에 콘솔에 1이 출력되고 countdown 0이 호출됩니다.
(그림으로 설명을 해보겠습니다. 👏👏😃)

0은 0보다 크지 않기 때문에 if문 수행 부분으로 들어가지 않고, countdown 0은 더 이상 재귀하지 않습니다.

그리고 countdown 0은 더 이상 재귀하지 않기 때문에 countdown 1도 더 이상 재귀하지 않고, countdown 2도 더 이상 재귀하지 않고, countdown 3도 더 이상 재귀하지 않고, countdown 4도 더 이상 재귀하지 않습니다.

countdown 4도 더 이상 재귀하지 않기 때문에 프로그램은 끝납니다.

👉재귀함수 사례(재귀패턴)

인터넷에는 재귀함수 관해서 개념 설명과 예시등은 아주 많습니다. 근데 정작 실전에서 언제 사용하는지 감이 오지 않죠?
이번 기회에 사례를 보여 드릴게요 FE 개발자가 실전에서 재귀함수를 언제 사용하는지 아래 예시를 봅시다.

만약 서버에서 부터 아래와 같이 생긴 JSON 데이터를 받아왔다고 가정해 봅시다.
comments라고 배열을 보면 안에 또 다시 comments 안에 또 다시 comments 안에 이런식의 구조로 되어 있습니다.
이런 상황일때 comments의 content를 화면에 출력해 봅시다.
어떻게 하면 좋을까요? 바로 이때 재귀함수를 사용하면 됩니다.

위에 데이터를 받아서 template에 데이터를 삽입하는 코드입니다.
makeComment라는 함수를 자세히 보면 재귀패턴을 사용 하고 있습니다.

function newsDetail() {
  const id = location.hash.substring(7);
  const newsContent = getData(CONTENT_URL.replace("@id", id));
  console.log(newsContent)
  let template = `
    <div class="bg-gray-600 min-h-screen pb-8">
      <div class="bg-white text-xl">
        <div class="mx-auto px-4">
          <div class="flex justify-between items-center py-6">
            <div class="flex justify-start">
              <h1 class="font-extrabold">Hacker News</h1>
            </div>
            <div class="items-center justify-end">
              <a href="#/page/${store.currentPage}" class="text-gray-500">
                <i class="fa fa-times"></i>
              </a>
            </div>
          </div>
        </div>
      </div>
      <div class="h-full border rounded-xl bg-white m-6 p-4 ">
        <h2>${newsContent.title}</h2>
        <div class="text-gray-400 h-20">
          ${newsContent.content}
        </div>
        {{__comments__}}
      </div>
    </div>
  `;

  function makeComment(comments, called = 0) {
    const commentString = new Array();

    for(let i = 0; i < comments.length; i++){
      commentString.push(`
        <div style="padding-left: ${called * 40}px;" class="mt-4">
          <div class="text-gray-400">
            <i class="fa fa-sort-up mr-2"></i>
            <strong>${comments[i].user}</strong> ${comments[i].time_ago}
          </div>
          <p class="text-gray-700">${comments[i].content}</p>
        </div>  
      `);

      if(comments[i].comments.length > 0){ // base case
        commentString.push(makeComment(comments[i].comments, called + 1)); // recursive case
      }
    }
    
    return commentString.join("");
  }

  container.innerHTML = template.replace("{{__comments__}}", makeComment(newsContent.comments));
}

더 이상 comments에 데이터가 없을때까지 commentString라는 빈 배열에 자기 자신을 계속 호출하므로써
데이터 구조 depth(트리 레벨)가 아무리 깊에 있다고 해도 계속 불러 올수 있습니다.

재귀함수는 메모리를 많이 차지하고 성능이 반복문에 비해 느립니다. 함수를 반복적으로 호출하므로, 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있다. 그래서 위에서 말했듯이 base case 와, recursive case를 생각해야 한다.

저작자표시

Contents

새소식

인기 검색어