재귀
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다
장점
- 프로그래밍을 수월하게 할수 있다
- 변수 사용을 줄여준다.
단점
- 반복문보다 메모리 사용량 많고 수행시간이 길어질수 있음
- 무한반복이 일어나게되면 에러가 발생함.
꼬리재귀
꼬리 재귀는 '재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는' 방법이다.
이 방식을 사용하면 이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 스택이 넘쳐나는 문제를 해결할 수 있게 된다.
꼬리 재귀 함수는 이름처럼 항상 함수의 꼬리부분(마지막)에서 실행되는데, return되기 전에 값이 정해지며 호출당한 함수의 결과값이 → 호출하는 함수의 결과값으로 반환된다.
예시
어느 회사엔 부서가 있습니다.
부서에는 여러 명의 직원이 있는데, 이를 배열로 표현할 수 있다. sales 부서의 John과 Alice라는 2명의 직원을 배열 요소로 표현해 보았다.
부서는 하위 부서를 가질 수 있습니다. development 부서는 sites와 internals라는 두 개의 하위 부서를 갖는다. 각 하위부서에도 직원이 있다.
하위 부서가 커지면 더 작은 단위의 하위 부서(또는 팀)로 쪼개질 가능성도 있다.
sites 부서는 미래에 siteA와 siteB로 나뉠 수 있다. 이렇게 나눠진 부서가 미래에 더 세분화될 수도 있다. 미래에 벌어질 일까진 나타내지 않았지만, 이러한 가능성도 있다는 걸 염두에 두어야 한다.
이제 모든 임직원의 급여를 더한 값을 구해야 한다.
반복문을 사용할 때 가장 먼저 떠오르는 생각은 company를 대상으로 동작하는 for 반복문을 만들고 한 단계 아래의 부서에 중첩 반복문를 돌리는 것이다. 그런데 이렇게 하면 sites 같은 두 단계 아래의 부서에 속한 임직원의 급여를 뽑아낼 때 또 다른 중첩 반복문이 필요하다. 세 단계 아래의 부서가 미래에 만들어진다고 가정하면 또 다른 중첩 반복문이 필요할 것입니다. 얼마만큼의 깊이까지 중첩 반복문을 만들 수 있을까? 객체를 순회하는 중첩 반복문의 깊이가 3~4개가 되는 순간 코드는 정말 지저분해질 것이다
재귀를 이용한 풀이법을 시도한다면 N개의 하위 부서가 있는 객체 – 각 하위 부서에 속한 임직원의 급여 합계를 얻기 위해 N번의 재귀 호출을 하고, 최종적으로 모든 하위부서 임직원의 급여를 더한다.
