재귀함수

(자연수) 리스트의 합을 구하는 알고리즘

1. 변수 sum을 0으로 초기화

2. 순차적으로 리스트의 구성요소에 접근하면서 sum을 더함

 

function arrSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

이 문제를 다른 각도에서 생각해보자.
자연수의 리스트 [10, 6, 4, 3]의 합을 구한다고 가정

 

1. [10, 6, 4, 3]의 합을 구하는 건 신경 쓰지 않고, 대신에 [6, 4, 3]의 합을 구하는 방법을 생각

2. [10, 6, 4, 3]보다는 [6, 4, 3]가 더 작으니 왠지 더 쉽게 풀릴 것 같다. [6, 4, 3]의 합을 구하는 방법을 알아낸다면, 이 값에 10을 더하면 원래의 목적인[10, 6, 4, 3]의 합을 구할 수 있음

3. [6, 4, 3]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [4, 2]의 합을 구하는 방법을 생각

4. [4, 2]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [2]의 합을 구하는 방법을 생각

5. [2]의 합을 구하는 건 매우 간단 => 2

 

이 과정을 간단한 코드로 표현

arrSum([10, 6, 4, 3]) = 10 + arrSum([6, 4, 3]);
arrSum([6, 4, 3]) = 6 + arrSum([4, 3]);
arrSum([4, 3]) = 4 + arrSum([2]);
arrSum([3]) = 3 + arrSum([]);
arrSum([]) = 0;

 

이처럼 어떠한 문제를 해결할 때,

구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 한다.

 

재귀 함수 사용 코드

function arrSum(arr) {
  let head = arr[0];
  let tail = arr.slice(1);

  if (arr.length === 0) {
    return 0;
  }

  return head + arrSum(tail);
}

 

스택 오버플로우(stack overflow)

함수는 메모리에 각자의 공간을 할당하고 이를 호출 스택에 할당한다.

함수가 계속해서 호출되다보면 메모리는 한정된 공간이므로 언젠간 가득 차서 함수를 호출할 수 없는 상황이 된다.

이때 발생하는 에러를 스택 오버플로우라고 한다.

 

재귀 함수와 메모리 사용량 간의 관계(javascript recursion memory leak)

- 재귀 함수는 반복문에 비해 메모리를 많이 차지

- 재귀 함수를 사용하면 함수를 반복적으로 호출하므로 스택 메모리가 커지고, 스택오버플로우가 발생할 수 있음

- 반복문 기반 알고리즘을 통해 알고리즘을 사용하여 메모리 절약

 

꼬리 재귀(tail call recursion)

재귀 함수의 위와 같은 단점을 보완하고자 꼬리 재귀라는 기법을 사용할 수 있다.

public int recursive(int n) {
  if (n == 1) {
    return 1;
  }
  return n + recursive(n - 1);
}

public int tailRecursive(int n, int acc) {
  if (n == 1) {
    return acc;
  }
  return tailRecursive(n - 1, n + acc);
}

두 함수의 큰 차이는 다음 호출을 위한 파라미터의 연산이 어디서 일어나는가의 차이이다.

 

즉, 다시 말해 return 문에 연산이 있느냐 없느냐 차이

 

꼬리 재귀는 연산이 return 문 이전에 이루어지고 다음 함수 호출 시 파라미터를 통해 필요한 연산의 결과를 전달하고

함수가 호출되는 시점에 컴파일러는 꼬리 재귀를 최적화하게 되는데, 이 과정에서 꼬리 재귀는 반복문으로 변경된다.

 

기존의 재귀 형태를 최적화 가능한 형태로 변경하면서 컴파일 시 반복문으로 해석될 수 있도록 만들면 기존에

문제였던 메모리와 성능에 대한 문제를 해결할 수 있다.