[JavaSrcipt] 재귀함수

✅ 재귀(Recursion)

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

재귀가 무엇인지 더 자세히 알아봅시다.

일단은 가장 유명한 재귀 예제를 한번 봅시다.

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

factorial(3);
// 6

이 예제는 제공된 정수의 팩토리얼을 반환합니다.

 

재귀의 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)함수의 결과 값으로 곱해진 어떤 값을 반환합니다.

 

✅ 예제

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

factorial(3);
// 6

 

예를들어, x에 10을넣었다면

10* factorial(9)를해야하는데 

factorial(9)의 값은

x즉 9 *factorial(8)

factorial(8)의 값은

x즉 8*factorial(7)

....... 쭉 진행하다

factorial(1)을 실행하면

x즉 1* factorial(0)인데

factorial(0)에서 x는0이므로 기반조건의 return 1을 반환한다.

그럼 다시 역으로 올라가며 

factorial(1)은 1* factorial(0)의값이 1을 반환했으므로 1*1 =1

factorial(2)는 factorial(1)의값이 1*1 즉 1을 반환했으므로 2*1 =2

factorial(3)는 factorial(2)의값이 2*1 즉 2를 반환했으므로 3*2 =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];가 재귀가 일어나는 코드 라인입니다.

종료 조건은 없습니다. 왜냐하면 이 예제에서는 기반 조건이 곧 종료조건이기 때문입니다.

문자열은 음수와 같은 특성을 가질 수 없습니다. 그래서 함수에 문자열이 들어오는 한, 괜찮습니다.

 

 

자바스크립트에서, substr() 메소드는 특정한 위치에서 시작하는 문자열을 반환합니다.

cat.substr(1) === 'at'와 같은 결과를 내보냅니다.

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

 

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

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

cat에서 revStr함수가 재귀되며 str의 0인덱스 즉

첫글자를제외한 다음부터 끝까지를 substr(1)메서드를 통해 내보내고 뒤에 0인덱스를 추가

 

하지만아까도 그랬듯 기반조건이 충족되지않았으므로

str이 ""이 될때까지 반복

 

revStr(t)까지 왔다면 revStr(str.substr(1))은 ""이고 str[0]은 t이므로

여기서 revStr(str.substr(1)) 이 ""었으므로 ""을 반환

즉 역으로 ""+'t'

 

 

revStr('t')는 ""+'t'를 반환

revStr('at')는  revStr(str.substr(1))즉 revStr('t') 이때 ""+'1'를 반환한다는것을 알고있음.

즉 str[0]='a'이므로 ""+'t'+'a'가 됨

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

 

 

-출처

https://velog.io/@jakeseo_me/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%9D%BC%EB%A9%B4-%EC%95%8C%EC%95%84%EC%95%BC-%ED%95%A0-33%EA%B0%80%EC%A7%80-%EA%B0%9C%EB%85%90-23-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%9E%AC%EA%B7%80Recursion-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0