재귀란

어떤 문제를 동일한 구조의 더 작은 문제로 나눠 각각을 해결함으로써 전체를 해결하는 방법
어떤 함수가 스스로를 호출하는 것

키워드 : 동일한 구조 + 더 작은 문제

재귀적 사고

1. input - output
2. input을 기준으로
   1)경우의 수를 나눈다
   2)반복되는 동일한 구조의 해결방법을 찾는다
3. 2-1 중 base case (탈출 조건)을 구현한다
4. 2-2 함수로 만들어서 recursive case를 구현한다

function arrSum(arr){ 
//1. input : [숫자] ouput : sum 
//2-1. (1) base case: arr =[] (2) recursive case: 이외 
//2-2. arr[1] + arrSum(arr.slice(1)) 

//Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초) 
if(arr의 길이가 0인 경우) { 
	return 0;
} 

//Recursive Case : 그렇지 않은 경우 
문제를 더 이상 쪼갤 수 없는 경우 
head : 배열의 첫 요소 
tail : 배열의 첫 요소만 제거된 배열 

return head + arrSum(tail);

}

재귀 함수의 템플릿

function recursive(input1, input2, ...){ 
//**Base Case: 문제를 더 이상 쪼갤 수 없는 경우 **
if(문제를 더 이상 쪼갤 수 없을 경우){ 
	return 단순한 문제의 해답; 
}

//recursive Case
//그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제 
someValue + recursive(input1Changed, input2Changed, ...)
someValue + recursive(input1Changed, input2Changed, ...)
}

factorial

function fac(n){
if(n===1){
return 1
}
return n * fac(n-1)
}

가장 내부에 있는 함수부터 실행되어서 값을 전달받는다

재귀함수의 작동 원리

본인 안에서 다시 호출된 함수는 콜스택에 쌓인다

5를 넣으면 4를 넣어서 호출되고 [스스로 복사해서 콜스택에 쌓는다] : callstack은 debugger로 확인 가능
4를 넣으면 3을 넣어서 호출되고
3을 넣으면 2를 넣어서 호출되고
2를 넣으면 1을 넣어서 호출된다