재귀함수와 꼬리재귀함수

1. 재귀함수

  재귀함수란 자기자신을 다시 호출하여 문제를 해결하는 함수이다. 주어진 문제가 비슷한 구조의 더 작은 문제로 나누어질 수 있거나, 중첩된 Loop가 너무 많은 경우, 중첩된 Loop의 중첩의 정도를 미리 알 수 없을 경우 사용한다.

 

  예를 들어 3!의 값을 구해보자. 3! = 3 * 2!로 나타낼 수 있으며 2! = 2 * 1!, 1! = 1*0!으로 나타낼 수 있다. 이 때 0보다 작은 factorial 값은 존재하지 않으므로 0! = 1이 가장 작은 factorial 값이 된다. 즉 다음 그림과 같은 상황인 것이다.

3! 구하기

 

  그림을 다시 코드로 나타내면 다음과 같다.

//factorial 구하기
function factorial(num) {
  if(num < 1){
    return 1;
  }
  return num * factorial(num-1)
}

//더 간결한 코드
function factorial(n){
  return n ? n * factorial(n-1) : 1;
}

 

  또 다른 예로 중첩된 배열을 1차원 배열로 만들어보자. [1, [2], [3, [[[4]]]], 5, [6, [7, [8]]]] 와 같은 배열을 [1,2,3,4,5,6,7,8]로 만드는 문제이다. 이 경우 for문으로 배열의 요소를 방문하면서 요소가 배열인 경우 다시 for문으로 해당 요소의 안으로 다시 들어가는 것을 반복하여 1차원 배열로 만들 수 있다. 그러나 중첩된 배열이 너무 많고, 중첩의 정도를 예상할 수 없으므로 재귀함수로 해결해야한다.

function flattenArr(arr) {
  let resultArr = [];
  for(let i = 0; i < arr.length; i++){
    if(!Array.isArray(arr[i])){
      resultArr.push(arr[i]);
    }else{
      resultArr = resultArr.concat(flattenArr(arr[i]))
    }
  }
  return resultArr;
}

 

2. 재귀함수 만들기

  재귀함수를 만들 때 구체적으로 다음과 같은 과정을 거쳐 함수를 작성한다.

1. ) 재귀함수의 입력 값과 출력 값을 설정한다.
2. ) 문제를 더 작은 문제로 계속 나눈다.
3. ) 가장 작은 문제를 해결한다.
4. ) 가장 작은 문제의 해결방법을 이용하여 복잡한 문제를 해결한다.

  일반적인 재귀함수의 기본 형식은 다음과 같다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case(복잡한 문제)
  return 더 작은 문제로 새롭게 정의된 문제 //ex. return input1 + recursive(...)
}

 

2. 재귀함수와 Memory

  모든 반복문은 재귀함수로 만들 수 있으며 코드가 간결하다는 장점이 있다. 그러나 모든 반복문을 재귀함수로 쓰는 것은 옳지 않다. 재귀함수는 함수를 문제의 가장 작은 경우(base case)에 도달할 때 까지 함수를 호출하며 더 작은 경우의 함수 호출 결과를 사용하여 최종 결과를 만든다. 그런데 현재 실행중인 함수가 끝나지 않은 채로 새로운 함수를 호출하므로 함수의 스택 프레임(실행 컨텍스트)이 콜 스택에 쌓이게 된다. 이는 스택 오버플로우가 발생할 수 있는 위험성이 있으며 재귀의 중첩의 정도(recursion depth)가 깊어질수록 메모리를 차지하는 단점이 있다. 따라서 재귀함수와 반복문을 적절히 선택하여 사용해야한다.

 

3.  꼬리재귀

  꼬리재귀란 재귀 함수를 호출할 때 현재 함수 호출까지의 값을 계산하여 함수를 끝내고 새로운 함수를 호출함으로써 함수 호출로 인한 스택이 쌓이지 않도록(스택을 덮어씌워 재사용 가능) 구현하는 방식이다. 위의 factorial 코드를 꼬리재귀로 구현하면 다음과 같다.

function factorial_tail(num, acc = 1){
  if(num < 1) { return acc; }
  else { return factorial_tail(num-1, num * acc)}
}

 

 

  꼬리재귀 코드는 재귀와 달리 현재 함수 실행 결과를 계산한 뒤 다음 재귀 함수로 전달하며 현재 함수에서 다음 재귀 실행 결과를 이용한 별도의 작업을 수행하지 않는다. 이러한 경우에는 앞으로 현재 실행 컨텍스트를 사용할 필요가 없기 때문에 이를 저장하지 않으며 현재 함수의 스텍 프레임 또한 쌓을 필요가 없다.(지금 실행한 함수 스택 프레임을 다음 함수가 덮어쓰면서 재사용한다.) 컴파일러는 위의 꼬리재귀 함수를 다음과 같이 해석한다.

function factorial_tail(num){
  let acc = 1;
  do
  {
    if (n == 1) return acc;
    acc = acc * n;
    n = n - 1;
  } while (true)
}

 

  위 코드와 같이 꼬리재귀는 단순 재귀일 때와 달리 함수를 일반 함수사용처럼 선형적으로 호출하므로 스택 프레임을 쌓지 않는 것이다. 이러한 꼬리재귀를 사용하기 위해서는 컴파일러가 이러한 최적화 기능을 지원하는지 확인하여야 한다.

 

 

---

참고 사이트

재귀와 스택

 

꼬리 재귀는 무엇입니까?