Udemy 자료구조 & 알고리즘 - 재귀

FE 개발자 신상오·2022년 6월 23일
0

재귀

자기 자신을 호출하는 함수로
문제를 더 이상 작게 쪼갤 수 없는 단위로 쪼갠 다음에
제일 작은 문제부터 쪼개기 전의 문제까지 차례대로 해결할 때 사용됨

  • 언제 주로 사용되는지?
  1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  2. 중첩된 반복문이 많거나 중첩 횟수를 예측하기 어려운 경우
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

모든 재귀는 반복문으로 표현 가능하지만 대부분의 경우에 재귀로 훨씬 간결한 코드를 짤 수 있습니다

재귀함수 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

재귀함수 예시

배열의 모든 요소의 합을 구하는 함수

const arr = [1, 2, 3, 4, 5];

function arrSum(arr){
	// basecase
	if (arr.length === 0){
    return 0;
    }
  
  	return arr[0] + arrSum(arr.slice(1));  
}

코드 해설

코드를 맨 앞 인덱스요소를 제외한 나머지 요소를 계속해서 재귀함수로 돌린다

문제가 가장 작은 단위로 나누어질 때까지 쪼갠다

  1. 1 + arrSum([2, 3, 4, 5])
  2. 1 + 2 + arrSum([3, 4, 5])
  3. 1 + 2 + 3 + arrSum([4, 5])
  4. 1 + 2 + 3 + 4 + arrSum([5])
  5. 1 + 2 + 3 + 4 + 5 + arrSum([])
  6. 1 + 2 + 3 + 4 + 5 + 0

선입후출 구조인 스택 형태로 동작한다.
가장 마지막에 들어간 6번부터 1번까지 순서대로 계산이 처리됨

profile
주간 회고용 블로그입니다 (개발일지와 정보글은 티스토리에 작성합니다.)

0개의 댓글