프로그램은 기본적으로 반복되는 작업을 수행하도록 설계가 된다. 반복을 구현하는 로직은 필수적이고 프로그래밍 언어마다 for , while 과 같은 기본적인 반복 제어문을 지원하고 있다.
반복되는 작업은 기본 반복 제어문을 통해서 뿐만 아니라 재귀 함수로도 구현 할 수 있는데, 하나의 함수가 자신을 다시 호출하여 반복되는 작업을 수행하는 함수를 재귀 함수라고 한다.
반복문과 재귀 함수는 서로 반복을 수행하는 구조는 다르지만, 재귀 함수로 작성 할 수 있는 코드라면, 반복문으로도 작성 할 수 있고, 반복문으로 작성 가능한 코드라면, 재귀 함수로도 작성 할 수 있다.
그래서 어떤 방식이 더 좋은건가?
반복문과 재귀 함수의 차이점에 대해 알아보자.
반복문
- 정의 : 일련의 명령을 반복적으로 실행할 수 있다.
- 체재 : 반복에는 초기화, 조건, 루프 내의 명령문 실행 및 제어 변수 업데이트가 포함
- 종료 : 특정 조건에 도달 할 때까지 반복적으로 실행
- 조건 : 반복문의 제어 조건이 참이라면 무한 반복이 발생
- 무한반복 : 무한 루프는 CPU 사이클을 반복적으로 사용
- 스텍 메모리 : 스텍 메모리를 사용하지 않음
- 속도 : 빠른 실행
- 가독성 : 코드 길이를 더 길게 만들고 변수가 많아 가독성이 떨어짐
재귀 함수
- 정의 : 함수 자체를 호출한다.
- 체재 : 기본적으로 종료 조건만 지정한다.
- 종료 : 조건부문은 함수 호출 본문에 포함되어 재귀 호출을 실해앟지 않고 함수를 강제로 반환한다.
- 조건 : 기본적으로 조건에 수렴하지 않으면 무한 재귀가 발생한다.
- 무한반복 : 무한 재귀는 스택 오버플로우를 일으킨다.
- 스텍 메모리 : 스텍 메모리는 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합을 저장하는데 사용
- 속도 : 느리다.
- 가독성 : 코드 길이와 변수가 적어 가독성이 높다.
왜 재귀 함수를 사용할까?
가독성을 제외하고선 장점이라고 없는 재귀 함수를 왜 사용하는 것일까?
변수 사용을 줄일 수 있다.
변수 사용이 줄어든다는 뜻은 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다는 뜻이다.
반복문
let sum = 0;
for (let i = 0; i <= 100; i++) {
sum += i;
}재귀 함수
function sum(n) {
if (n === 100) return n;
else retur n + sum(n + 1);
}
sum(0);위 코드들은 전부 0부터 100까지의 합을 구하는 코드이다.
일반적인 반복문의 경우 sum , i 라는 2개의 변수를 가지게 되고, 재귀 함수의 경우 n 이라는 1개의 변수를 가지게 된다. 이렇게 보면 큰 차이가 없어보일 수 있지만 프로젝트의 크기가 커지거나, 단순한 반복문이 아닌 변수가 10개 100개가 들어가야하는 반복문이라고 가정하고 생각했을 경우, 지나치게 많은 변수 선언으로 인한 예상치 못한 side effect를 막을 수 있다.
재귀적 표현이 자연스러운 경우
재귀 함수의 대표적인 예시인 피보나치 수열은 결과값으로 1,1,2,3,5,8 ... 의 값을 가지게 되는데, 이를 식으로 나타내보자면 다음과 같다.
반복문
function fibonacci(n) {
let pre = 0;
let cur = 1;
let last = 0;
for (let i = 1; i < n; i++) {
last = pre + cur;
pre = cur;
cur = last;
}
return last;
}재귀 함수
function fibonacci(n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}기본적으로 모든 반복문은 재귀 함수로 표현 할 수 있고, 재귀 함수는 반복문으로 표현 할 수 있다고 하였다. 대개 재귀 함수가 반복문에 비해 가독성이 좋은 경우가 많고, 위와 같은 예시에서는 재귀적으로 문제를 푸는 것이 자연스럽게 느껴진다. 이러한 경우에는 재귀 함수를 사용하는 것이 더 올바른 코드 작성법이 될 것 같다.
재귀 함수의 치명적 단점 해결 - 꼬리 재귀
재귀 함수의 가장 큰 문제로 자기 자신을 호출 한 뒤 결과를 기다리면서 생기는 콜 스텍의 부하로 인한 메모리낭비였는데, 꼬리 재귀라는 개념을 이용하게 된다면 재귀 호출이 끝나는 시점에 아무 일도 하지 않고 결과를 바로 반환하도록 하는 방법으로 함수의 상태 유지 및 추가적인 연산을 처리하지 않기 때문에 스텍 오버플로우 현상을 해결 할 수 있다.
결론
재귀는 반복문보다 느리고 성능이 좋지 않지만, 반복문보다 가독성이 좋고 유지보수에 이점이 있다. 현업에서의 사용은 반복문보다 재귀를 선호하는 편이며 기본적인 프로그래밍 실력을 키우고 싶다면 재귀를 자주 사용하고 연습하는 것이 좋을 것 같다.
