재귀함수의 정의
재귀함수는 자신을 다시 호출하는 함수이다. 그리고 이러한 호출의 반복을 끊어주기 위해서는 반드시 종료 조건인 base case를 제대로 설정해줘야 한다. Base case가 제대로 되있지 않으면, 무한 루프같은 상황이 발생해서 Call Stack이 터지게 된다.
그리고, 재귀함수로 작성되는 코드는 반복문으로도 작성할 수 있다.
그러나, 어떤 상황에서는 for나 while같은 반복문으로는 매우 까다롭거나, 코드가 매우 길어지는 상황에서 재귀는 강력한 힘을 발휘한다.
=> 그래서, 이제부터는 어떤 상황에서 재귀가 강력한 힘을 발휘하는지 알아보자.
재귀가 반복문보다 적합한 상황
재귀는 특히 아래와 같은 상황에서 매우 적합하다.
1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우
그런데, 이렇게만 봐서는 딱히 와닿지 않으니, 예시를 하나 들어보자!!
다음 배열 안의 숫자의 총합을 구하려면 어떻게 해야할까??
=> 일단, 이 문제의 핵심은 배열 안에 요소들이 전부 숫자가 아니라 또다른 배열일 수도 있다는 점이다.
이것을 for문으로 작성해보면, 다음과 같다.
이 문제를 반복문으로 작성할 수 있는 이유는 배열 속에 배열이 몇 단계까지 넘어갈지 알 수있기 때문이다.
그러나, 이런 상황이라면, 어떨까??
배열 안에 배열이 있을 수도 있고, 그게 몇 단계로 내려갈지 알 수도 없는 상황이라면, 매번 for문으로 처리해주는 것은 불가능할 것이다.
왜냐하면, 몇 단계로 내려가는지 모른다면, 얼마나 많은 하위 for문을 if절로 처리해줘야 될지도 모르기 때문이다.
물론, 위치를 저장하는 방식으로 다 처리하게 짤 수는 있겠지만, 코드가 매우 복잡하고 지져분해진다.
하지만, 재귀함수로 이 문제를 작성한다면, 애초에 몇 단계까지 넘어가야 될지 걱정할 필요가 없다.
=> 배열의 요소가 숫자면, 그대로 더하고!!
=> 배열이라면, 재귀로 똑같이 파고들도록 한다.
즉, 이러한 상황처럼 여러 단계를 포함할 수 있는 데이터를 다루는 경우에는 재귀가 강력한 힘을 발휘한다.
이외에도, 하노이의 탑과 조합(combination) 문제가 재귀함수의 좋은 예시가 될 수 있다. 이 두가지 예시를 재귀함수로 짠 것과 반복문으로만 짠 케이스를 나눠서 비교해보는 것도 좋은 학습이 될 것같아서, 조만간 시도해볼 예정이다.
재귀 함수의 문제점
다만, 이 재귀 함수에는 성능 문제가 있다.
재귀 함수는 호출될 때마다 메모리에 스택이 쌓이게 된다. 다시 말해서, 한계치 이상으로 호출되서 콜 스택이 넘쳐버리면, 메모리 부족으로 에러가 발생한다.
또한, 속도 면에 있어서도 재귀 함수는 반복문보다 시간을 더 소모한다.
이런 문제를 해결하기 위해, 많은 언어들에서 " 꼬리 재귀 최적화 "라는 기능을 제공한다.
자바스크립트에서는 ES6 스펙 상에는 tail recursion optimization이 명시되어 있다. 하지만, 아직까지는 Chrome의 V8엔진은 꼬리 호출 최적화를 지원하지 않고 있다. 현재 브라우저 중 꼬리 호출 최적화를 지원하는 브라우저는 Safari 뿐이라고 한다.
그렇다면 자바스크립트에서 재귀를 사용할 일이 없을까??
자바스크립트 실무에서는 비동기 프로그래밍이 많이 쓰이며, 비동기가 일어나면 스택이 초기화되므로 재귀 사용을 피할 이유는 없다.
ex)
필자의 경우는 재귀함수의 Call Stack이 터지는 것을 방지해주기 위해서,setTimeout()으로 재귀 함수를 감싸줘서, 비동기적으로 만들어준다.
필자 역시 꼬리 호출 최적화가 모든 환경에서 동작하기를 간절히 바라지만, 우선은 재귀를 아쉬운대로 이용할 수 밖에 없다.
예시 문제
재귀함수를 이용한 1부터 100가지의 합과 곱
// 1-100까지 합 구하는 법
// 1. for 문
// i번 반복 되기 때문에, O(n)
let sum = 0;
for ( let i = 0; i < 101; i++ ){
sum += i;
// console.log("sum is", sum); => 5050
}
console.log(sum);
문제에 적용할 수 있는 수학 공식이 있는지 반드시 찾아보자
- 시그마 공식을 이용한 솔루션
바로 실행이 되기 때문에 O(1)
그래서 항상 풀고자 하는 문제가 수학 공식이 있는지 찾아보고 푸는 게 좋다. 효율 차이가 엄청나다.
// 2. 시그마 공식
let n = 100;
console.log( n*(n+1)/2 );
// 3. 재귀 함수로 풀기
// sum의 횟수만큼 반복되기 때문에 O(n)
function sumTo100 (sum){
if( sum <= 0 ){
return 0;
}
return sum + sumTo100(sum-1);
}
console.log( sumTo100(100) );
재귀함수를 이용한 "피보나치"
피보나치 수열의 중요성
피보나치 수열이 수학적으로 중요한 이유는 여러 가지가 있는데, 그중 하나는 이 수열이 황금비를 만든다는 것이다. 즉, n+1번째 피보나치 수를 n번째 피보나치 수로 나누면 그 비율은 점차 1.6으로 수렴한다.
고대인들은 황금비에서 신비로움을 찾은 것과 동시에 이것으로부터 어떤 안정된 즐거움을 찾았다. 학자들은 고대 그리스로부터 중세에 이르기까지 많은 건축물과 조각상에서 피보나치 수와 황금비를 찾았다. 대표적으로 그리스의 조각가인 피디아스의 조각에서, 파르테논 신전과 다른 그리스 건축물에서 그리고 1180년대에 세워진 크루니 대 수도원에서 찾을 수 있다.
오늘날의 과학기술에서 피보나치 수열이 나타나는 경우는 너무 많다. 이 수열은 데이터를 분류하고 정보를 검색하는 데에도 이용되고 있다. 최근에는 암호는 물론 컴퓨터과학 분야에서 광범위하게 쓰이고 있다. 특히 약 100년 전, 독일의 심리학자 페흐너(Gustav Fechner)는 수백 명에게 여러 종류의 직사각형을 보여 준 다음, 마음에 드는 것을 선택하게 하는 실험을 했다. 그런데 그 결과 대부분 황금 직사각형을 선택했다고 한다.
가로의 길이와 세로의 길이의 비가 8:5 즉 ‘8/5 =1.6’인 황금 직사각형은 다양한 제품의 디자인에 활용되고 있으며, 디스플레이 화면에서도 이러한 비율을 찾아볼 수 있다. 예를 들어 갤럭시노트 10.1 2014 에디션과 2019년 8월에 출시된 갤럭시 탭 S6의 화면의 가로와 세로의 비율이’ 16:10 =8:5’로 황금 직사각형이다.
이는 제품 디자이너가 소비자에게 더욱 아름다운 영상을 제공하려는 깊은 고민의 결과라고 생각된다. 이처럼 황금 직사각형을 빈번하게 이용하는 이유는 무의식중에도 아름다움을 추구하는 우리의 잠재의식 때문일 것이다. 앞으로도 황금비, 피보나치 수열이 적용된 다양한 제품이 나올 거라 예상해 본다.
자료출처 - 삼성디스플레이 뉴스룸
자료출처 - 위키백과
(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
- for문을 이용한 방법
// n은 n 번쨰 피보나치 수열
// (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
// 1번째는 1부터 시작한다.
function Fibonacci(n){
let a = 1;
let b = 1;
let result = 0;
if( n<3 ){
return 1;
}
else{
// a => n-2 번째
// b => n-1 번째
for( let i=0; i<(n-2); i++ ){
result = a + b;
a = b;
b = result;
}
}
return result;
}
Fibonacci(16); // 987
- 재귀함수로 피보나치 수열 구현
// n은 n 번쨰 피보나치 숫자
// (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
// 1번째는 1부터 시작한다.
function Fibonacci(n){
if( n < 3 ){
return 1;
}
else{
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
Fibonacci(16); // 987
자료 출처
이번 블로그는 " 코드스테이츠 "의 강의 내용의 일부와 아래의 자료들을 참고하여 작성했으며, 그 어떠한 상업적 용도도 없음을 밝힌다.
