재귀: 어떤함수가 스스로 호출하는것
팩토리얼로 알아보자
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]
- arr = [1, 2, 3] -> head = 1 return [3, 2].concat(1) // [3, 2, 1]
그렇게 해서 [3,2,1]이라는 결과가 나온다
