정리_JavaScript - 재귀함수 (Recursion)

재귀: 함수가 자기 자신을 호출하는 순간

 

모든 재귀 함수는 3가지 key feature를 가져야 한다.

1. A Termination Condition

if (something bad happened ) { STOP };

fail-safe. 비상 브레이크.

재귀함수의 무한 반복 방지.

 

2. A Base Case

if (this happens) { Yay! We're done };

 

3. The Recursion

함수가 자기 자신을 호출하도록 한다.

 

 

 

예시1)

function factorial(x) {
  if (x < 0) return;   // TERMINATION
  if (x === 0) return 1;   // BASE
  return x * factorial(x - 1);   // RECURSION
}
factorial(3);
// 6

이것을 실행시키면

factorial(3)

= 3 * factorial(2)

= 3 * 2 * factorial(1)

= 3 * 2 * 1 * factorial(0)

= 3 * 2 * 1 * 1 → return (Base Case)

 

 

 

예시2)

function revStr(str){
  if (str === '') return '';   // BASE
  return revStr(str.substr(1)) + str[0];   // RECURSION
}
revStr('cat');
// tac

여기서는 Base Case = Termination Case라서

Termination Case가 따로 없다.

 

substr() 메소드는 string의 ()안의 위치부터 끝까지 반환한다.

 ex) 'cat'substr(1) === 'at'

 

str[] 메소드는 []안의 인덱스의 글자를 반환한다.

 ex) cat[0] === 'c'

 

 

 

그래서 이것을 실행시키면

return revStr(str.substr(1)) + str[0]   // cat
→ return revStr('at') + 'c'   // tac

→ return revStr('t') + 'a'   // ta

→ return revStr('') + 't'   // t

→ if (str === '') return '';   ↑거꾸로 올라가면

 

→ return ‘’ + ‘t’ + ‘a’ + ‘c’   // tac

 

 

https://codeburst.io/learn-and-understand-recursion-in-javascript-b588218e87ea

Learn and Understand Recursion in JavaScript