TIL 2020-11-18 (재귀)

nyongho·2020년 11월 18일
0

JavaScript

목록 보기
12/23
post-thumbnail

Week 4-2 : 재귀적으로 생각하기


TIL List

  • 재귀의 이해
  • 재귀적 사고 연습하기

1) 재귀?

국어사전에 따르면 재귀란 "원래의 자리로 되돌아가거나 되돌아옴." 이라고 적혀있다.
따라서 재귀 함수란, 자기 자신을 호출(리턴)하는 형태의 함수다. 반복되는 형태라는 점에서 반복문 (For, Whlie) 과 같다고 할 수 있다.

특정 배열의 요소의 합을 구하는 코드를 짜본다고 가정해보자.

반복문에 대해 충분히 이해했다면 별 문제 없이 다음과 같이 코드를 짤 수 있을 것이다.

let arr = [1,2,3,4,5];
function getArrSum (arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum = sum + arr[i]
  }
  return sum; // getArrSum(arr) === 15 -> true
}

위와 같이 반복문을 통해 arr 의 요소의 합을 쉽게 구할 수 있다.

이번엔 위 문제를 재귀적 사고 로 바라봐보자.


2) 재귀적 사고 연습하기

  1. arr의 요소인 [1,2,3,4,5] 의 총합을 구해야 하므로 총합은 1 + 2 + 3 + 4 + 5 가 돼야한다.
  1. 한 번에 계산하는건 복잡하니 하나씩 접근해보자. 2 + 3 + 4 + 5 의 합을 먼저 구해본다.
  1. 이것도 복잡하니 3 + 4 + 5 의 합을 구해본다.
  1. 좀 더 간결하게 먼저 4 + 5 의 합을 구해본다.

위 문제를 재귀적 사고 를 통해 코드로 작성한다면 다음과 같을 것이다.

arrSum([1,2,3,4,5]) = 1 + arrSum([2,3,4,5]) = 1 + 14 = 15
arrSum([2,3,4,5]) = 2 + arrSum([3,4,5]) = 2 + 12 = 14
arrSum([3,4,5]) = 3 + arrSum([4,5]) = 3 + 9 = 12
arrSum([4,5]) = 4 + arrSum([5]) = 4 + 5 = 9
arrSum([5]) = 5 + arrSum([]) = 5 + 0 = 5
arrSum([]) = 0;

문제를 잘개 잘개 쪼개서 하나하나씩 해결해 나가는 과정을 볼 수 있다.

이와 같이 재귀적 사고 는 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀적 사고(recursion)라고 한다.
사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능하지만, 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고, 일부의 경우에는 이해하기도 쉽다.

하지만 위 코드에는 문제점이 있다. 바로 탈출 조건이 명시돼있지 않다는 것이다.

따라서 저 코드는 자신이 언제까지 이 짓을 반복해야하는지도 모른채 끝 없는 반복을 거치다가 결국 MAXIMUM CALL STACK 이란 처절한 결과를 나타낼 것이다.

여기서 알 수 있는건 재귀 함수 또한 반복문과 같이 탈출 조건을 반드시 명시해줘야 한다는 점이다.

따라서 탈출조건은 다음과 같이 설정할 수 있다.

1. 만약, arr의 길이가 0일 경우, 즉 빈 배열일 경우 0 을 리턴한다.

2. 1번을 이용해 arr의 요소를 모두 돌아서 arr의 요소가 더 이상 존재하지 않을 때까지 반복한다.

3. 그 외의 경우는 첫 요소 arr[0] 에 나머지 배열을 모두 더한다.

이제 이것을 코드로 작성해본다면 다음과 같을 것이다.

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

function arrSum(arr) {
  if (arr.length === 0) { // 탈출 조건
    return 0;
  } 
  const head = arr[0]; 
  const tail = arr.slice(1);  
  return head + arrSum(tail)
}

arrSum(arr) // 15

위를 봐도 저 코드가 어떻게 작동되는지 이해가 잘 안될 수 있다. 아래는 위 코드가 작동되는 과정이다.

head = [1] tail = [2,3,4,5]  // 처음 함수 실행 시 head, tail 의 값
return [1] + arrSum([2,3,4,5])

head = [2] tail = [3,4,5]  // return 을 통해 다시 실행된 함수의 head, tail 값
return [2] + arrSum([3,4,5])

head = [3] tail = [4,5]  // return 을 통해 다시 실행된 함수의 head, tail 값
return [3] + arrSum([4,5])

head = [4] tail = [5]  // return 을 통해 다시 실행된 함수의 head, tail 값
return [4] + arrSum([5])

head = [5] tail = []  // return 을 통해 다시 실행된 함수의 head, tail 값
return [5] + arrSum([0])

// tail이 빈 배열, 즉 입력받은 arr이 빈 배열이므로 조건문에 따라 0을 리턴한다.
// arrSum 에 0의 값을 받았으므로 역순으로 다시 올라가면서 합을 구한다.

5 + 0  = 5       //  return [5] + arrSum([0])
5 + 4 = 9        //  return [4] + arrSum([5])
9 + 3 = 12       //  return [3] + arrSum([4,5])
12 + 2 = 14      //  return [2] + arrSum([3,4,5])
14 + 1 = 15      //  return [1] + arrSum([2,3,4,5])

변수 head 를 기준으로 tail 의 요소 하나하나를 더하는 것을 볼 수 있다.

profile
두 줄 소개

0개의 댓글