내가 나를 호출 하는 함수
그럼 특수한 경우는 뭔가???
<1. 대표적 재귀함수 : factorial>
function factorial(n) {
if(n <= 1) { // 이부분이 종료 조건
return n
}
return n * fectorial(n-1)
}
factorial(5) = 120
// factorial(5) == 5 * factorial(4) == 5 * 24
// factorial(4) == 4 * factorial(3) == 4 * 6
// factorial(3) == 3 * factorial(2) == 3 * 2
// factorial(2) == 2 * factorial(1) == 2 * 1
// factorial(1) == 1
<2. 대표적 재귀함수: sigma>
function sigma (n) {
if(n <= 1) { // 이부분이 종료 조건
return n
}
return n * sigma(n-1)
}
factorial(5) = 15
// factorial(5) == 5 + factorial(4) == 5 + 10
// factorial(4) == 4 + factorial(3) == 4 + 6
// factorial(3) == 3 + factorial(2) == 3 + 3
// factorial(2) == 2 + factorial(1) == 2 + 1
// factorial(1) == 1
<3. 글자 거꾸로 쓰기>
function reverse(text) {
text +=''
if(text.length <= 1) {
return text
}
return reverse(text.slice(1)) + text[0]
}
// reverse('hello') == reverse('ello') + 'h' == 'olle' + 'h'
// reverse('ello') == reverse('llo') + 'e' == 'oll' + 'e'
// reverse('llo') == reverse('lo') + 'l' == 'ol' + 'l'
// reverse('lo') == reverse('o') + 'l' == 'o' + 'l'
// reverse('o') == 'o'
<4. 피보나치 수열>
function fib (n) {
if(n <= 2) { // 이부분이 종료 조건
return n
}
return fib(n-1) + fib(n-2)
}
// 왼쪽 function만 따라갔으니
// fib(4) == fib(3) + fib(2)
// fib(3) == fib(2) + fib(1) == 3
// fib(2) == 2
// fib(1) == 1
// 오른쪽 값인 fib(2)를 다시 해야하는 상황!!
// fib(2) == 2
// 반복문, 다이나믹 프로그래밍(메모이제이션(하향식), 타뷸레이션(상향식))
let fibo_cache = []
function fibo(n){
if (n in fibo_cache) {
return fibo_cache[n]
}
fibo_cache[n] = n < 2 ? n : fibo(n-2) + fibo(n-1)
return fibo_cache[n]
}
3 in [1,2,4,4,5]
true
우선은 피보나치 수열로 재귀함수를 이해해보고, 좀 더 발전 할 수 있도록
방향을 잡아야 겠다.