재귀 함수 정리

재귀: 어떤함수가 스스로 호출하는것

팩토리얼로 알아보자
5! = 5 x 4 x 3 x 2 x 1

다르게 작성하면

5! = 5 x 4!
5! = 5 x 4 x 3!
5! = 5 x 4 x 3 x 2!

이런식으로도 표현 할 수 있다 이걸 함수로 작성하면

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

fac(5)
return 5 x fac(4)
fac(4)
return 4 x fac(3)
fac(3)
return 3 x fac(2)
fac(2)
return 2 x fac(1)

fac(1) === 1 // 종료조건에 걸리고 다시 돌아감

fac(2)
return 2 x 1
fac(3)
return 3 x 2
fac(4)
return 4 x 6
fac(5)
return 5 x 24

결과 fac(5) === 120

재귀를 사용하는 경우
1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도를 미리 알 수 없는 경우

재귀함수는는 재귀 호출 없이 반복문으로 표현이 가능하다
하지만 재귀를 사용하면 코드가 간결해지고 이해 하기가 쉽다
또한 알고리즘 문제에서 유용하게 쓰인다

예제

function reverseArr(arr) { [1, 2, 3]
  if(arr.length  === 0){  
    return []
  }

  let head = arr[0] 
      tail = arr.slice(1)

  return reverseArr(tail).concat(head)
}

let output = reverseArr([1, 2, 3]);
console.log(output); // --> [3, 2, 1]

위 문제에서 재귀는 다음과 같이 사용된다
1. arr = [1, 2, 3] -> head = 1, tail = [2,3]
종료조건에 안 걸려서 reverseArr(tail) 새로운 함수로 실행
2. arr = [2, 3] -> head = 2, tail = [3]
종료조건에 안 걸려서 reverseArr(tail) 새로운 함수로 실행
3. arr = [3] -> head = 3, tail= []
let reverseArr(tail) = []
return [].concat(3) // [3]
종료조건에서 걸렸다 그 전 함수로 돌아가서 return reverseArr(tail)부분에 [3]을 할당한다
4. arr = [2, 3] -> head = 2 return [3].concat(2) // [3, 2]

5. arr = [1, 2, 3] -> head = 1 return [3, 2].concat(1) // [3, 2, 1]

그렇게 해서 [3,2,1]이라는 결과가 나온다