Recursive(재귀) vs Iterative(반복)
보통 Recursive와 Iterative가 많이 비교되곤 한다. Iterative는 '반복적인'이란 뜻을 가지고 있다. 즉, 우리가 흔히 사용하는 for 문이나 forEach 문과 같은 반복 연산을 가리킨다. 항상 그런 것은 아니지만 많은 경우에 Recursion으로 처리할 수 있는 문제는 Iterator로도 처리할 수 있고, 반대로 Iterator로 처리할 수 있는 것은 Recursion으로 처리할 수 있다. 어떤 방법으로 문제를 해결하느냐는 프로그래머의 마음이지만 때로는 Iterative 코드보다 Recursive 코드를 사용했을 때 더 이해하기 쉬운 코드가 될 때가 있다. 그러므로 우리는 두 가지 방법을 모두 명확하게 알고 있어야 한다.
재귀 함수란(Recursion Function)?
재귀의 뜻 그대로 재귀 함수란, 다시 돌아오는 함수 즉 자기 자신을 다시 호출해 작업을 수행하는 방식이다. 그렇기 때문에 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용하게 된다.
우리가 흔히 알고 사용하는 for , while , reduce 등이 있는데, 이러한 반복문으로 구현 가능한 로직은 모두 재귀함수로도 가능하고 그 반대로도 역시 가능하다.
재귀 함수는 큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴이다. 목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화 시킬 수 있을 때도 재귀를 사용할 수 있다.
재귀 함수의 개념
재귀적으로 문제를 풀기 위해서는 문제를 같은 형태의 더 작은 문제로 쪼개야하기 때문에 패턴을 찾아야 한다.
재귀 함수를 쓸 때는 항상 두 경우가 있어야 한다.
base case: 더 이상 문제를 쪼갤 필요가 없는 종료된 경우
recursive case: 문제를 쪼개서 풀어가는 경우
아주 간단한 예시를 살펴보면,
function factorial(num) {
if (num <= 1) { // base case
return 1
}
return num + factorial(num - 1) // recursive case
}
console.log(factorial(4)) //결과값 10
// 재귀패턴 순서 설명
// return 최종
// factorial(4) 4 + 3 + 2 + 1
// factorial(3) 3 + 2 + 1
// factorial(2) 2 + 1
// factorial(1) 1 (base case에 걸린 경우)재귀 함수의 대표적인 예시로 많이 활용되는 팩토리얼 함수에 대한 예시이다.
이 함수는 일반적으로 반복문을 사용해서 풀이한다면 이런 코드가 나올 것이다.
function factorial(num) {
let result = 1;
for (let i = n; i >= 1; i--) {
result *= i;
}
return result;
}반복문으로 작성할 수 있는 모든 코드는 재귀함수로 작성 할 수 있다.
그러면 왜 재귀 함수로 작성해야 하는 것일까? 장점은 무엇이 있고 단점은 무엇이 있을까?
재귀 함수의 장단점
장점
- 변수를 여럿 만들 필요가 없다. 현재 상태를 저장해야 할 경우 변수를 만들기보다 상태를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있다.
while문이나for문과 같은 반복문을 사용하지 않아도 되기 때문에 코드가 간결해진다.
단점
- 함수의 호출이 스텍에 쌓이게 되고, 차례대로 값을 반환하기 전에는 계목 메모리 공간을 차지하고 있다. 그렇기 때문에 호출 스텍이 너무 커져 메모리를 엄청나게 소비하여 속도, 성능이 저하될 수 있다. 반복문의 사용이 성능이 더 좋은 경우가 많다. 상황에 따라 적절한 방법을 골라 사용할 수 있어야만 한다.
