Recursion

가장작은 러시안돌 안에는 초콜렛이 들어있다.
초콜렛을 찾을때가지 러시안돌을 열어보는 코드를 작성해야한다면?
만약 인형이 총 몇개인지 안다면 for loop문을 사용해서 반복적으로 열어볼 수 있다.
하지만 몇개인지 모른다면 재귀함수를 사용해서 열어야 한다.

재귀함수는 크게 2가지 파트로 나뉜다. Base case, Recursive call
basecase는 끝나는지점이다. 이경우에는 초콜릿을 찾은경우
Recursive call은 반복하는 함수 그 자체이다.
이경우에는 다음의 작은 인형을 열어보는 동작이다.

두가지 파트를 유의하며 수도코드를 읽어보자.

function processDoll(doll)
{
// 1)Base case
if(found the piece of chocolate) //기반조건 - 우리의 목적
   return "yum";
// 2) Recursive call to itself
else if( there are no more dolls) // 종료조건 - 좋지않은 입력값이 들어왔을때 대처
  return "No chocolate here ";
else
 processDoll(the smaller doll) // 재귀 - 문제의 크기 줄이기
}

재귀함수는 함수 그 자신을 호출한다는 의미도 있지만 어떻게 보면 문제를 점점 더 작게
만들어간다는 의미도 있는것 같다.

예제1. 팩토리얼

function factorial(x){
  if(x <0){  // 종료조건 - 음수의 팩토리얼은 구할수없기때문에 종료시킨다.
    return ;
  }
  else if(x===0){ // 기반조건 - 우리의 목적
    return 1;
  }
  else return x * factorial(x-1); // 재귀 - 문제의 크기 줄이기
}

예제2. 문자열 거꾸로 뒤집기

function revStr(str) {
  if (str === '') return ''; // 기반조건 - 우리의 목적
  return revStr(str.substr(1)) + str[0]; //재귀 - 문제의 크기 줄이기
}

revStr('cat')
// tac

subter()는 특정위치부터 시작하는 문자열을 반환한다.

return revStr('at') + 'c'; // 재귀 - 문제의 크기 줄이기
return revStr('t') + 'a';
return revStr('') + 't';
if(str === '') return ''; // 기반조건 - 우리의 목적
return '' + 't' + 'a' + 'c'; // 최종결과