[알고리즘] 재귀

LMH·2022년 12월 15일

이번 포스팅은 주니어 개발자들이 꼭 한 번은 마주치게 되는 관문이며 그리고 통곡의 벽이라고도 물리는 재귀에 대해서 정리하고자 합니다.

재귀

재귀의 사전적 의미는 "원래 자리로 되돌아가거나 되돌아옴" 입니다. 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고 작은 문제를 해결함으로써 전체 문제를 해결하는 방법입니다. 재귀를 사용하는 코드는 간결하고 한눈에 이해하기 쉽습니다.

재귀를 사용하는 이유

재귀를 사용 이용해서 해결할 수 있는 문제는 대부분 반복문을 사용해서 해결할 수 있습니다. 하지만 반복문의 중첩이 굉장히 많아서 코드가 복잡한 경우 코드를 더 간단하게 만들어 줄 수 있습니다. 그리고 복잡한 알고리즘에 재귀를 사용하는 경우가 있기 때문에 개발자라면 개념을 이해하고 있어야 합니다.

재귀적로 문제해결 하기

재귀함수를 이용하여 간단문 문제를 해결하도록 하겠습니다. 아래의 코드는 배열 내부에 있는 숫자의 합을 리턴하는 구하는 재귀 함수를 표현한 것 입니다. 리턴문을 보면 arr의 첫번째 요소를 제거하고 그 값을 arrSum 함수 자신을 다시 한번 호출한 값과 더해줍니다.

function arrSum(numArr) {
  	if(numArr.length===0) {
    	return 0;
    }
	return numArr.shift() + arrSum(arr)
}

arrSum([1,2,3,4,5]) // 15

1. 재귀함수의 입력값과 출력값 정의하기

가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것입니다. 함수의 입출력값을 정의하는 것은 그 첫 출발점이며, 재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다.

arrSum은 number 타입의 배열을 입력 받아 number 타입을 리턴합니다.

arrSum: [number] => number ← 입출력값 정의

1. 문제를 작게 쪼개기(가장 작은 단위까지)

위의 코드를 더 간단하게 쪼갠다면 다음과 같이 나타낼 수 있습니다. 코드를 순서대로 쪼개어보면 배열 내부의 요소들의 합을 구하는 코드인 것을 쉽게 알 수 있습니다.

arrSum([1,2,3,4,5]) === 1 +  arrSum([2,3,4,5]) 
arrSum([2,3,4,5]) === 2 + arrSum([3,4,5]) 
arrSum([3,4,5]) === 3 + arrSum([4,5]) 
arrSum([4,5]) === 4 + arrSum([5]) 
arrSum([5]) === 4 + arrSum([])
// 입력받는 배열의 길이가 0이되면 0을 리턴해주면서 제귀에서 탈출합니다.

2. 문제 해결하기

문제를 쪼개어나 나가다가 더 이상 작아지지 않는 순간에 재귀에서 탈출하면서 원하는 결과값을 얻을 수 있습니다. 문제를 여러 경우로 구분하고 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)라고 부르며, 이것은 나중에 재귀의 탈출 조건이 될 수 있습니다.

탈출 조건이 없다면 재귀는 무한정 자신을 호출하기 때문에 콜 스택이 넘치는 상황이 발생합니다. base case를 작성한 후에 더 복잡한 문제를 해결하는 순서로 코드를 작성 합니다.

arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

3. 코드 구현하기

아래는 예시는 재귀함수의 기본적인 템플릿이며, 재귀함수는 더 다양한 방법으로 사용할 수 있습니다.

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

재귀함수의 성능

재귀함수는 복잡한 문제를 간단하게 해결한다는 점에서 매력적인 문제해결 방안이 될 수 있습니다. 하지만 재귀함수를 사용할 때는 시간 복잡도를 고려해야합니다. 재귀의 깊이가 깊어질 수록 그 알고리즘은 시간 복잡도가 증가하며 알고리즘의 성능은 낮아집니다.

피보나치 수열(시간복잡도 O(2^n))

피보나치 n번째 항의 값이 n-1, n-2 번째 항의 값의 합과 같은 수열입니다.
ex) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

아래와 같이 정의된 피보나치 수열 n번째 항의 수를 구하는 재귀함수를 구현하면 다음과 같습니다.

function fibonacci(n) {
	if(n===0) return 0;
	if(n===1) return 1;
  
	return fibonacci(n-1) + fibonacci(n-2)
}

반복문을 사용해서 푸는 것에 비해서 매우 간단하게 피보나치 수열의 n번째 항을 구할 수 있습니다. 예를 들어 5번째 항을 구하려면 3,4번째 항을 구하기 위해 함수가 반복해서 실행됩니다. 이 함수는 2번씩 트리의 높이 k 만큼 반복하는 형태로 시간 복잡도는 O(2^n)입니다. 이것은 O(n^2), O(n^3) 보다 성능이 좋지 못합니다.

개선된 피보나치 수열(시간 복잡도 O(n))

위의 코드를 훨씬 더 성능이 좋은 코드로 작성할 수 있습니다. 그 방법은 배열을 사용한 메모리제이션입니다. 피보나치 수열의 각 요소를 배열에 넣어 메모리에 저장해 두었다가 이미 배열에 값이 있는 항은 재귀함수를 호출 하지 않아 성능이 향상됩니다.

fibo라는 재귀함수를 내부에 선언하고 그 함수를 호출시키면서 배열에서 값을 얻어오는 구조입니다.

function fibonacci(n) {
	const arr = [0, 1];
  
  function fibo(n) {
  	if(arr[n] !== undefined) {  // n항에 대한 값이 arr 내부에 있으면 그 값을 리턴
    	return arr[n]
    } else {
       arr[n] = fibo(n-1) + fibo(n-2) // n-1, n-2번째 항을 더해서 배열의 n번째 요소에 넣기
        return arr[n]
    }
  }
  return fibo(n) 
}