8/30[TIL]재귀함수

어제 학습한 고차 함수에 이어 오늘은 재귀...
재귀는 기본적인 개념은 이해하고 있지만 사용하는 것에 정말 익숙해지고 싶은 부분이다. 실로 정말 깔끔한 코딩을 할 수 있기 때문이다. 구조가 비슷하면서 주어진 문제가 더 작은 문제가 나누어질 수 있고 중첩된 루프가 많거나 중첩된 정도를 미리 알 수 없을 때 for, while 문으로 해결을 했지만 이렇게 진행을 한다면 하드코딩을 감당해야 한다. 쪼개서 문제를 해결하는 방법을 재귀라고 예시와 함께 강의에서 말씀해주셨는데 이해하기 쉬웠던 것 같다. 문제를 더 이상 더 작아지지 않을 때까지 만든 후에 자기 자신을 호출하기도 하는 재귀 호출을 사용해서 코딩을 하는 것이다. 예시를 보고 아 이렇게 하면 되겠다 싶었는데 막상 내가 사용하려고 하니 그게 마음처럼 잘 되지 않는 것 같다. HA에서도 재귀를 사용하는데 정말 많은 시간이 들었다. 자연스러워질 때까지 많은 연습이 필요한 것 같다.

재귀는 반복문으로 표현 할 수 있고 깔끔한 코딩을 가능하게 해 주지만 재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야 한다고 한다. 그렇지 않으면 무한 루프에 빠진다는...ㅠㅠ 재귀로 코딩을 하게 되면 깔끔한 코딩은 물론 가독성이 좋다고 볼 수 있지만 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하기 때문에 메모리를 많이 사용하게 된다. 그리고 성능 자체가 반복문보다 늦다고 한다.

하지만 꼬리 재귀(?)라는 것을 이용하면 위와 같은 문제점을 해결 할 수 있다고 하는데 꼬리 재귀란 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태라고 한다. 아래를 보면 알 수 있다. 꼬리 재귀의 장점을 얻기 위해서는 개발자가 재귀 함수를 꼬리 재귀 방식으로 개발하여야 하며 컴파일러가 꼬리 재귀 최적화를 지원해야 한다는 전제조건이 있어야 한다고 한다. 컴파일러가 꼬리 재귀를 최적화할 수 있으면 최적화 과정에서 꼬리 재귀를 반복문으로 변경하는 방식인 것이다. 그럼 기존의 재귀의 단점인 메모리 성능의 문제가 해결되는 것이다.

function recursion(n) {
    if (n === 0) {
        return 1;
}
return n * recursion(n-1);
}
// 일반적인 재귀
 
function recursion(n, acc) {
    if (n === 0) {
        return 1;
}
return recursion(n-1, acc*n);
}
// 꼬리 재귀
 
 

재귀를 사용하여야 할 부분과 반복문으로 충분히 가능한 상황을 잘 판단하여야겠다는 생각을 했다.