자바스크립트 개발자라면 알아야 할 33가지 개념 #23 자바스크립트 : 자바스크립트 재귀(Recursion) 이해하기

Jake Seo·2019년 6월 19일

33concepts-of-javascript

목록 보기

23/27

들어가기 전에

이 포스팅은 https://codeburst.io/learn-and-understand-recursion-in-javascript-b588218e87ea 에 있는 포스팅을 번역한 것입니다. 오역이나 의역이 있을 수 있습니다. 지적해주시면 확인 후 바로 정정하겠습니다.
original source of this posting is from https://codeburst.io/learn-and-understand-recursion-in-javascript-b588218e87ea If the original author requests deletion, it will be deleted immediately.

Translated by Jake Seo (서진규)

	- https://velog.io/@jakeseo_me
	- https://github.com/n00nietzsche

자바스크립트 개발자라면 알아야 할 33가지 개념 #23 자바스크립트 : 자바스크립트 재귀(Recursion) 이해하기

재귀(Recursion)이 뭘까요?

재귀를 간단하게 정의하면 한 함수가 자기 자신을 호출하는 순간입니다.

재귀가 무엇인지 더 자세히 알아봅시다. 일단은 가장 유명한 재귀 예제를 한번 봅시다. 이 예제는 제공된 정수의 팩토리얼을 반환합니다.

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

factorial(3);
// 6

위의 예제가 잘 이해가 되지 않더라도 괜찮습니다. 중요한 부분은 4번째 라인에서 일어납니다. return x * factorial(x - 1);. 여러분도 보고 있듯, 함수가 자기 자신을 다시 호출하고 있습니다. (factorial(x-1)), 하지만, 처음에 호출했던 값보다 1 작아진 파라미터와 함께 다시 호출됩니다. 4번째 라인과 같은 구문이 이 함수를 재귀함수로 만들어줍니다.

코드 예제를 더 설명하기 전에 알려드리고 싶은 것은, 팩토리얼의 개념을 먼저 잘 이해하는 것이 매우 중요하다는 것입니다.

어떤 수의 팩토리얼을 구하기 위해서, 우리는 어떤 숫자의 -1을 구하여 1이 될 때까지 곱해야 합니다.

예제 1: 4의 팩토리얼은 4 3 2 * 1, 24

예제 2: 2의 팩토리얼은 2 * 1, 2

훌륭합니다. 이제 고등학교 수학 시간은 끝났습니다. 다시 좋은 것들을 배우러 떠나봅시다.

. . .

재귀의 3가지 중요한 특성

모든 재귀 함수는 3가지의 중요한 특성을 갖습니다.

종료 조건

간단하게, if(나쁜 값이 들어왔다면) { 정지! };과 같이 이해하시면 됩니다. 종료 조건은 재귀의 안전장치입니다. 종료 조건을 여러분들의 긴급 브레이크처럼 생각하세요. 좋지 않은 입력 값이 들어왔을 때, 재귀가 계속하여 동작하는 것을 방지해줍니다. 위의 팩토리얼 예제에서, if (x < 0) return;은 우리가 설정한 종료 조건입니다. 음수의 팩토리얼을 구하는 것은 불가능합니다. 그래서 우리는 음수 입력 값이 들어왔을 때, 팩토리얼 함수가 작동하지 않길 원합니다.

기반 조건(Base case, 기저 상태)

간단하게, if(이런 일이 일어난다면) { 성공! }과 같이 이해하시면 됩니다. 이 조건 역시 재귀 함수를 멈춘다는 점을 감안하면, 기반 조건은 어쩌면 재귀의 종료조건과 비슷합니다. 하지만 종료 조건은 모든 나쁜 데이터들을 잡아낸 다는 것을 기억하세요. 반면에 기반 조건은 재귀 함수의 목적 입니다. 기반 조건은 주로 if 문 내부에 있습니다. 팩토리얼 예제에서는, if (x === 0) return 1;이 기반 조건이었습니다. x가 0까지 내려갔을 때, 우리는 팩토리얼을 구하는데 성공한 것입니다!

재귀

간단하게, 함수가 자기 자신을 호출하는 것입니다. 팩토리얼 예제에서, return x * factorial(x -1);부분이 실제로 재귀가 일어나는 곳입니다. 우리는 숫자 x가 factorial(x-1)함수의 결과 값으로 곱해진 어떤 값을 반환합니다.

위의 3가지를 동시에 봅시다.

여전히 팩토리얼 예제가 어떻게 동작하는지 정확히 모를 수도 있겠죠. 아래 예제가 도움을 줄 겁니다.

function factorial(x) {
  // 종료 조건
  if (x < 0) return;
  
  // 기반 조건
  if (x === 0) return 1;
  
  // 재귀
  return x * factorial(x - 1);
}

factorial(3);
// 6

팩토리얼 함수 흐름

우리가 팩토리얼 함수를 호출했을 때 정확히 어떤 일들이 벌어지는지 다시 한번 체크해봅시다.

우리는 숫자 3을 넘겨서 함수를 호출합니다.

factorial(3);

함수가 동작하게 됩니다. if문을 넘어가고 재귀 부분을 실행합니다. 정수 3과 factorial(3-1)이 곱해진 결과를 반환합니다.

return 3 * factorial(2);

factorial(2)가 동작할 때, if을 다시 넘어가고 재귀가 일어납니다. 정수 2와 factorial(2-1)이 곱해진 결과를 반환합니다.

return 2 * factorial(1);

factorial(1)이 동작할 때, if문이 또 한번 넘어가게 되고 재귀가 일어납니다. 정수 1과 factorial(1-1)이 곱해진 결과를 반환합니다.

return 1 * factorial(0);

factorial(0)이 동작할 때, 뭔가 다른 일이 일어납니다. 0은 우리의 기반 조건입니다. 그래서 if문에 걸려 함수는 1을 반환합니다.

if(x === 0) return 1;

이제 함수가 마침내 리턴을 마쳤습니다. 궁금했던 모든 것들이 풀렸을 것입니다. 재귀는 단순히 중첩된 함수 호출이기 때문입니다. 모든 중첩된 함수에서 가장 내부에 중첩된 함수가 가장 먼저 반환됩니다.

이 부분을 이해하는 것은 매우 중요합니다. 처음 보자마자 이해가 되지 않았다면, 이 부분을 몇번 읽어보세요.

factorial(0) 는 1

factorial(1) 는 1 * factorial(0), 또는 1*1

factorial(2) 는 2 * factorial(1), 또는 2*1*1

factorial(3) 는 3 factorial(2), 또는 `3211`

return 1 * 1 * 2 * 3
// 6

잘 따라 오셨나요? 같은 구조로 되어 있는 다른 예제입니다.

factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)
factorial(0) returns 1
// 여기서 기반 조건이 충족됩니다. 재귀 함수는 안에서 부터 바깥으로 값을 반환해나갑니다.
factorial(0) returns 1                 => 1
factorial(1) returns 1 * factorial(0)  => 1 * 1
factorial(2) returns 2 * factorial(1)  => 2 * 1 * 1
factorial(3) returns 3 * factorial(2)  => 3 * 2 * 1 * 1
// 3 * 2 * 1 * 1 = 6

여전히 잘 이해가 되지 않더라도 괜찮습니다. 이제 다른 예제를 구경해보고 헷갈렸던 부분들을 말끔히 해봅시다.

. . .

두번째 예제를 봅시다

두번째 예제는 완전히 다른 방향으로 갈 것입니다. 이 예제 또한 인터넷에서 유명한 예제입니다. 문자열을 거꾸로 뒤집는 것과 관련된 예제입니다.

우리가 앞으로 구현할 방법이 자바스크립트에서 문자열을 뒤집기 위해 가장 효율적인 방법은 아님을 알아두세요. 훨씬 빠른 방법들이 많습니다. 이건 그냥 인터넷에 존재하는 가장 흔한 재귀 예제입니다. 그래서 이 예제를 다루는 것입니다.

코드는 다음과 같이 생겼습니다.

function revStr(str) {
  if (str === '') return '';
  return revStr(str.substr(1)) + str[0];
}

revStr('cat')
// tac

위의 코드 예제를 보고 알 수 있는 몇가지가 있습니다.

str === ""는 우리의 기반 조건(base case)입니다. 문자열 내부에 아무런 글자도 남아있지 않을 때, 우리는 목적을 달성한 것입니다.
return rev(str.substr(1)) + str[0];가 재귀가 일어나는 코드 라인입니다.
종료 조건은 없습니다. 왜냐하면 이 예제에서는 기반 조건이 곧 종료조건이기 때문입니다. 문자열은 음수와 같은 특성을 가질 수 없습니다. 그래서 함수에 문자열이 들어오는 한, 괜찮습니다.

한줄 한줄 쪼개봅시다.

이 예제에서, 우리는 cat이라는 문자열을 뒤집습니다. 시작 부분에서 cat이라는 문자열을 넘기며 함수를 호출합니다.

revStr('cat');

재귀함수가 동작합니다.

자바스크립트에서, substr() 메소드는 특정한 위치에서 시작하는 문자열을 반환합니다. cat.substr(1) === 'at'와 같은 결과를 내보냅니다.

str[0]는 문자열에서 첫 인덱스에 위치한 문자를 내보냅니다. cat[0] === 'c'와 같은 결과를 내보냅니다.

return revStr(str.substr(1)) + str[0];

// 아래와 같습니다.
return revStr('at') + 'c';

재귀가 다시 한번 동작합니다.

return revStr(str.substr(1)) + str[0];

// 아래와 같습니다.
return revStr('t') + 'a';

재귀가 마지막으로 동작합니다.

return revStr(str.substr(1)) + str[0];

//아래와 같습니다.
return revStr('') + 't';

이번엔 기반 조건이 동작하고, 함수가 빈 문자열을 반환합니다.

if(str === '') return '';

이제 함수가 결과를 반환합니다. 모든 것이 풀렸고 순서대로 반환합니다.

return '' + 't' + 'a' + 'c';
// tac

더 잘게 쪼개봅시다.

추가로, 여기서 차례차례 다시 진행해봅니다.

revStr('cat')  returns revStr('at') + 'c'
revStr('at')   returns revStr('t') +  'a'
revStr('t')    returns revStr('') +   't'
revStr('')     returns               ''

이제, 여기 중첩된 함수 호출들이 있습니다. 중첩된 함수 호출을 갖고 있을 때, 가장 안쪽 함수가 가장 먼저 실행됩니다. 계속 리턴을 하며, 쌓인 재귀를 풀어나가기 시작하는 과정입니다.

revStr('')     returns                ''  => ''
revStr('t')    returns revStr('') +   't' => '' + 't'
revStr('at')   returns revStr('t') +  'a' => '' + 't' + 'a'
revStr('cat')  returns revStr('at') + 'c' => '' + 't' + 'a' + 'c'
// tac