재귀함수 1부 (재귀함수의 의미)

재귀함수란?

mdn에서의 정의는 함수가 자기 자신을 호출하는 행위 이며 더 작은 부분 문제들을 해결하기 위해 사용된다... 란다.

간단히 말해서 어떠한 문제를 해결하기 위해 자기 자신을 호출하는 함수이다.

(출처:https://developer.mozilla.org/en-US/docs/Glossary/Recursion)

 

자기 자신을 반복적으로 호출하는 것이기 때문에 반복문으로도 작성이 가능하다.

고롬 한번 간단하게 작성해보자!

 

재귀함수를 이용한 factorial 함수

const factorial = (n) => {
  if (!n) return 1;		//base case
  return n * factorial(n - 1);	//recursive case
};
factorial(4);

위처럼 재귀함수를 이용하여 factorial 함수를 만들어보았다.

factorial의 수식은 n! = n × (n-1) × (n-2) × (n-3) × (n-4) ×  … × 4 × 3 × 2 × 1 이며 주어진 값과 그값에 -1 하여 서로 곱하고 마지막 값이 1이 될때까지 계속해서 반복해주는 식이다.

 

재귀함수를 만듦에 있어서 제일 중요한점은 base case와 recursive case를 작성해 주어야한다.

base case란 함수가 중단되는 시점, 위의 함수에서는 if문이 base case가 되고

recursive case는 재귀호출이 발생되는 위치, 즉 if문 뒤의 return 값이 되겠다.

 

만약 recursive case를 설정해주지 않을경우 함수가 작동하지 않을것이고 base case를 설정해주지않을경우...

이런 에러가 발생할것이다...

자바스크립트 런타임에 스택이 무한대로 쌓이게되어 나타나는 에러이다.

 

재귀함수와 반복문의 비교

const factorial = (n) => {
  let result = 1;
  for (let i = n; i > 0; --i) {
    result = result * i;
  }
  return result;
};
factorial(4);

위의 같은 결과를 내는 반복문과 재귀함수를 비교해 보니 장단점이 뚜렷하게 나왔다.

 

재귀함수의 장점

두 함수를 비교해봤을때 확실히 재귀함수가 가독성도 좋고 코드의 수도 짧았다. 뿐만아니라 변수를 사용할 필요도 없어서 프로그래머의 실수를 줄일수 있는 장점들을 가지고 있다.

하지만 마냥 좋은것만은 아니다. 

 

재귀함수의 단점

함수가 끝나지 않고 반복적으로 사용되다보니 자바스크립트 런타임에 스택이 계속해서 쌓이게된다. 결국 메모리사용이 증가하고 속도저하가 발생하게된다.

과연 해결할수 있을까??

 

해결책 내놔

재귀함수의 단점을 해결하기위해 나온것이 바로 꼬리 재귀!

const factorial = (n, a = 1) => {
  if (!n) return a;
  return factorial(n - 1, n * a);
};
factorial(4);

 

 

꼬리 재귀의 경우 하나의 파라미터를 더 받으며 일반 재귀 함수는 다음 함수를 불러 그 값을 받아와 연산을 하지만 꼬리 재귀의 경우 두 파라미터를 이용하여 연산을 한뒤 다음 함수에 넘겨주게 되는것이다. 

(굉장히 중요하니 별2개 그리고 밑줄 3줄 긋자.)

 

재귀 - 다음 함수의 리턴값을 받아온 후 연산

꼬리 재귀 - 연산후 내 리턴값을 다음 함수로 넘겨줌

 

그렇다면 왜?? 뭣땜시 뭐시가 다른거시여?

이전 포스트에서 함수 호출시 자바스크립트 런타임에 스택이 쌓이게되고 그 스택들에 의해서 블로킹현상이 발생할수도 있다는 것을 알수 있었다. 

(이전포스트:https://mason-lee.tistory.com/6)

 

그렇다면 재귀와 꼬리 재귀의 런타임 스택을 살펴보자.

재귀의 스택

 

꼬리 재귀의 스택

 

위와 같은 차이점이 나는 이유는 스택은 함수가 종료되거나 return 값을 받아야 스택에서 빠저나올수있다.

일반 재귀의 경우 첫번째 함수가 return이 되기 위해선 다음 함수의 값들이 줄줄이 필요하기때문에 계속해서 스택이 쌓이지만 꼬리재귀의경우 함수 자체를 리턴하기때문에 첫번째 함수가 연산을 끝내면 스택에서 빠저나온뒤 다음 함수가 실행되는 구조이기 때문이다.

또한 이러한 이유로 재귀함수에는 꼭! base case를 작성하여 엔드포인트를 만들어주어야한다.

(블로킹 실제사례:https://jslim.net/blog/2019/11/28/Becareful-of-JavaScript-blocking-the-main-thread/)

 

다음 글에서는 예제를 이용한 재귀함수의 사용을 포스트하겠습니다.