Javascript_재귀함수

재귀함수

내가 나를 호출 하는 함수

• 시간 변환, 콤마 등등에서 사용
• 실무에서 권하진 않음 (가독성이 떨어짐)
• 특수한 경우 말고는 사용하지 마라!!
• 공식 몇가지 외워놓고 사용하기

그럼 특수한 경우는 뭔가???

• 네비게이션에서 최단 경로 찾는 거

1) 재귀함수의 조건

1. 종료 조건(like 긴급 브레이크)
2. 반복문으로 구현할 수있는 것은 재귀함수로 모두 구현 가능
   • 재귀함수로 구현 가능한 것은 반복문으로 대부분 구현 가능하다.
   • 복잡도를 증가시키면 모두 구현 가능합니다.

<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

• 함수는 최종값만 남고 휘발된다.
• 호출되는 것이 메모리를 차지하고 있으므로 아래 기법을 적절히 믹싱해서 사용할 필요가 있음
• 제가 짠 코드는 해당 index의 값이 아니라 해당 index까지의 합입니다.

// 반복문, 다이나믹 프로그래밍(메모이제이션(하향식), 타뷸레이션(상향식))
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]
}

• 1번이랑 다른 점은 어딘가(cache)에 저장되고 있다는 점
• 메모이제이션 된다
• (n in fibo_cache) -> cache언애 n번째 인덱스 (값이 아님)

3 in [1,2,4,4,5]
true

---

우선은 피보나치 수열로 재귀함수를 이해해보고, 좀 더 발전 할 수 있도록
방향을 잡아야 겠다.