서론
오늘은 어제와 그제 공부한 재귀를 이용해서 알고리즘 문제를 몇 개 풀어보았다.
그 중 하나는 배열로 받은 데이터를 내부에서 비교하고 조건에 해당하는 데이터를 찾아내 배열로 다시 반환하는 문제였는데, 재귀를 이용해서 구현하다보니 문제가 하나 생겼다. 재귀함수는 계속해서 함수 내부에서 자기 자신을 호출한다. 그렇기 때문에 함수 내부에 반환할 데이터의 배열을 선언하면 다시 이 함수를 호출했을 때 선언했던 배열이 다시 선언되고 데이터가 없는 텅 빈 배열이 되는 것이다.
나는 이 문제를 함수 밖에 전역변수로 변수를 선언하면서 해결했지만, 내부에 선언하고도 이 문제를 해결 할 수 있는 방법을 오늘 소개하고자 한다. 그 이름은 다음과 같다.
- Helper Method Recursion
- 순수재귀 솔루션
본론
1. Helper Method Recursion
이건 내가 듣고있는 강의에서 강사분이 설계하고 있는 일종의 패턴으로 외부함수를 정의하고 그 안에 내부함수로 재귀를 정의하는 식의 패턴이다.
Helper Method Recursion 장점
- 변수를 함수 밖에 선언할 필요없이 함수안에 선언하고 데이터를 수집할 수 있다. 모든 필요한 코드가 동떨어져 있지 않고 한 곳에 모여있다.
- 간단하고 가시성이 좋다.
Helper Method Recursion 예시문제
function findOdds(arr){
let result = [];
function mathOdds(arr2){
if(arr2.length === 0) return;
if(arr2[0] % 2 !== 0) result.push(arr2[0]);
mathOdds(mathOdds.slice(1))l
}
mathOdds(arr)
return result;
}다음과 같이 재귀는 함수 전체에서 일어나는 것이 아니라 변수가 선언된 하단에서만 일어나기 때문에 선언한 변수를 초기화 시키지 않고 데이터를 수집할 수 있게 된다.
2. 순수재귀 솔루션
위와 같은 패턴을 이용하지 않고 순수재귀만을 이용해서 모든 필요한 코드를 함수 안에 포함하면서 솔루션을 작성할 수 있다. 순수재귀 솔루션에서는 재귀외부에 함수를 하나 더 호출하여 배열을 초기화하는 것을 피하지 않고 함수를 호출할때마다 배열을 새로이 정의한다. 하지만, 계산이 완료되었을 때 모든 배열을 하나의 배열로 합쳐서 반환한다.
순수재귀 솔루션 장점
- 마찬가지로 변수를 함수 밖에 선언할 필요없이 함수안에 선언하고 데이터를 수집할 수 있다.
- 더 간결하게 코드를 구현할 수 있다.
순수재귀 솔루션 예시문제
function findOdds(arr){
let result = [];
if(arr.length === 0) return result;
if(arr[0] % 2 !== 0){
result.push(arr[0]);
}
result = result.concat(findOdds(arr.slice(1)));
return result;
}이런식으로 순수재귀 솔루션을 사용하면 좀 더 복잡하지만 helper method recursion 패턴보다는 간결하게 솔루션을 구현할 수 있다. 어떤 방식으로 데이터가 초기화 되는 것을 막고 있냐면 우리가 이전에 배웠던 팩토리얼 방식과 같은 유형으로 데이터를 전해주고 있기 때문이다.
매번 재귀에서 새로운 result가 선언이 되고, 홀수일 때 홀수의 값을 result에 push한 뒤 함수를 호출한다. 함수는 concat 뒤에 호출이 되는데 이전 팩토리얼을 구현한 함수처럼 다음 스택에서값이 반환될 때까지 이전스택의 함수는 대기를 한다.종료점까지 재귀가 진행된뒤, 종료점에서부터 값이 리턴으로 전해지면서 모든 배열이 concat으로 이어진다.
이렇게 스택이 아래에서 위로 쌓이고 위에서 아래로 진행된다는 점을 이용해서 데이터를 계속 수집할 수 있는 재귀 솔루션을 작성할 수 있다. 마지막으로, 순수재귀 솔루션을 사용할 때에는 몇 가지 팁이 있는데 강의에서 소개했던 것들을 나도 여기 적어보려고 한다.
Tip
배열을 사용해서 순수재귀 솔루션을 작성할 때 > slice, spread operator, concat 사용 가능
문자열은 변경할 수 없으니, slice나 substring같은 사본을 만들어야 한다.
객체의 경우에는 Object.assign이나 spread operator을 사용하는게 유용하다.
참고
