[Algorithm] 반복문(iteration) vs 재귀(recursion)

지금까지 반복적인 작업이 필요한 알고리즘 문제들~~(거의 필연적인..?)~~을 풀면서 일반 반복문(while, for)이나 재귀함수를 번갈아가며 사용했었다. 하지만 코드나 접근방식에 오류가 생겼을 때, 발생하는 현상은 달랐다.

일반 반복문은 시간 초과(무한 루프), 재귀함수는 stack overflow가 발생했다.

재귀함수의 경우 stack이라는 메모리 공간을 계속 이용하기 때문에 메모리의 제한이 있는 한 stack overflow가 뜨면서 메모리가 터진다고 한다. 반복문의 경우에는 메모리를 이런식으로 사용하지 않아 단지, 프로그램이 종료되지 않을 뿐이다.

그렇다면 재귀함수의 경우 반복문에 비해 메모리를 많이 사용한다는 확연한 단점을 가지고 있는데 왜 자주 사용하게 될까? (사실 나 또한 while이 어색해서 재귀함수를 많이 쓰곤한다..ㅎ) 한번 알아보도록 하자!

반복문과 재귀함수

프로그램은 반복되는 작업을 수행하도록 설계된다. 따라서 반복을 구현하는 로직은 필수적이고 프로그래밍 언어마다 for, while 같은 기본적인 반복 제어문을 지원한다. 즉 반복문의 정의는 명령을 반복적으로 실행하는 것 그 자체다.

이때 반복되는 작업은 기본 반복 제어문뿐 아니라 재귀함수로도 구현할 수 있다.

재귀함수의 정의는 하나의 함수가 자신을 다시 호출하여 반복되는 작업을 수행하는 함수다.

반복문 vs 재귀함수

처음 의문점의 답을 알기 전에 반복문과 재귀함수의 차이점에 대해 알아보자.

	반복문	재귀함수
정의	명령을 반복적으로 실행	함수를 다시 호출하여 반복작업 수행
스택 메모리	스택 메모리를 사용하지 않음	함수 호출 시 함수의 매개변수, 지역변수, 리턴값, 함수 종료 후 돌아가는 위치가 스택메모리에 저장
무한 반복 시	무한 루프는 CPU 사이클을 반복적으로 사용	무한 재귀는 스택 오버플로우 발생
속도	빠른 실행	느린 실행

※ 스택오버플로우(stack overflow)란?
재귀함수 사용 시, 함수를 반복적으로 호출하므로, 스택메모리에 콜 스택이 쌓이게 된다. 이때 함수를 호출하는 횟수가 많아진다면 스택메모리를 초과하여 stack overflow가 발생하는 것이다. (일반적인 반복문 사용 시, 지역 변수들이 호출될 때 한번만 할당되기 때문에 이러한 일이 발생하지 않는다.)

왜 재귀함수를 사용할까?

아무리 봐도 단점밖에 보이질 않는 재귀함수! 느리고.. 메모리를 사용하고..

그럼에도 불구하고 재귀함수를 사용하는 이유는 무엇일까?

1. 변수 사용을 줄일 수 있다.

변수 사용이 줄어든다는 뜻은 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다는 뜻이다.

일반 반복문

let sum = 0;
for(let i = 0; i <= 100; i++) {
  sum += i;
}

재귀 함수

function sum(x) {
  if(x === 100) return x;
  else return x + sum(x + 1);
}

sum(0)

위의 코드들은 전부 0부터 100까지의 합을 구하는 코드다.

일반 반복문의 경우 sum, i 라는 2개의 변수를 가지고

재귀 함수의 경우 x라는 1개의 변수를 가진다.

사실 지금은 별 차이가 없어보이지만 좀 더 많은 변수를 사용할 일이 생길 때 조금이나마 변수를 줄일 수 있다. 이를 통해 예상치 못한 side effect 를 막을 수 있다!

2. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 (+ 가독성)

재귀함수하면 너무나 유명한 예시인 피보나치 수열은 1, 1, 2, 3, 5, 8 ... 의 값을 가지는 데 이를 식으로 나타내보자면 다음과 같다.

f(n) = f(n - 1) + f(n - 2)

일반 반복문

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(num) {
  if(num < 2) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

위의 두 예시를 비교해보자면 재귀 함수의 경우 더욱 직관적임을 알 수 있다! 사실 알고리즘을 풀 때 재귀함수를 자주 사용했던 이유들을 생각해보면 가독성이 좋다는 이유가 가장 컸던 것 같다!

꼬리 재귀

재귀 함수또한 여러 장점들을 가지고 있지만 메모리를 많이 사용한다는(+ stack overflow)라는 큰 문제점을 갖고 있는데.. 이러한 단점을 보완하고자 꼬리 재귀 기법이란 것이 나왔다!

(단, 컴파일러가 꼬리 재귀 최적화를 지원해야만 실질적으로 단점을 보완할 수 있다.)

아래 일반 재귀, 꼬리 재귀 코드를 보도록 하자.

// 일반 재귀
function sum(x) {
  if(x === 100) return x;
  else return x + sum(x + 1);
}

sum(0)

// 꼬리 재귀
function tailSum(x, answer) {
  if(x > 100) return answer;
  else return tailSum(x + 1, answer + x)
}

tailSum(0, 0)

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

일반 재귀의 경우 함수가 return 된 후에 연산이 일어나고

꼬리 재귀의 경우 return 문 이전에 연산이 일어난다.

즉, 차이점은 return 문에 연산이 있냐 없냐이다.

꼬리 재귀가 호출되는 시점에 컴파일러는 꼬리 재귀를 최적화하고, 이 때 꼬리 재귀는 반복문으로 변경된다. 이를 통해 기존의 문제였던 메모리와 성능에 대한 단점을 해결할 수 있게 되었다.

정리

재귀 함수를 사용하여 반복 구조를 구현하면 복잡한 문제도 직관적으로 알 수 있고, 이는 협업에서 코드의 가독성이라는 이점이 될 수 있다. 하지만 콜 스택이 쌓여 stack overflow로 인한 메모리의 폭발이 일어날 수 있다는 단점을 가지고 있다. 이는 꼬리 재귀라는 기법을 통해 대비할 수 있지만, 무작정 방심할 수는 없다. 따라서 재귀 함수를 사용할 때 어느정도 함수를 호출하게 될 지 예측을 하고 안전하게 사용하는 것이 좋을 것 같다!

제원's 개발공부