[자료구조] 재귀 함수

Jun·2022년 6월 23일

TIL 자료구조

자료구조 / 알고리즘

목록 보기

1/10

재귀 함수

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

재귀 함수 (Recursive function)는 자기 자신을 호출하는 함수를 말한다.

반복적인 작업을 해야하는 문제에서 재귀 함수를 사용한다면 문제를 좀더 간결한 코드로 풀어낼 수 있다.

function recursion () {
  console.log("This is");
  console.log("recursion!");
  recursion(); // 자기 자신을 다시 호출
}
// This is와 recursion!이 무한히 반복되어 출력된다.

재귀로 문제 해결하기

재귀로 문제를 해결할 때 다음과 같은 절차를 따른다.

문제를 작게 나누기
문제를 가장 작은 단위로 나누기
문제 해결하기

순서에 따라 전달받은 자연수 배열([1,2,3,4,5])의 합을 반환하는 함수(arrSum)를 작성해보자.

1. 문제를 작게 나누기

arrSum 함수로 [1,2,3,4,5] 의 합을 구하는 과정을 더 작게 나눠보자.

arrSum([1,2,3,4,5]) === 1 + arrSum([2,3,4,5]);
arrSum([2,3,4,5]) === 2 + arrSum([3,4,5]);
...

2. 문제를 가장 작은 단위로 나누기

1번에서 문제를 나눈 방식을 반복하여 계속 나누다보면 더이상 나눌 수 없는 상태에 도달한다.

arrSum([3,4,5]) === 3 + arrSum([4,5]);
arrSum([4,5]) === 4 + arrSum([5]);
arrSum([5]) === 5 + arrSum([]);
// 더 이상 나눌 수 없다.

arrSum([5]) 를 나누었을때 arrSum() 이 빈 배열을 전달받으며 문제를 더 이상 나눌 수 없게 되었다. 즉 가장 작은 단위까지 나눴다고 할 수 있다.

3. 문제 해결하기

문제가 더 이상 나눠지지 않으면, 가장 작은 단위의 문제를 해결한다. 나눌 때 같은 방식으로 나눴기 때문에, 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결 가능하다.

2번에서 구한 가장 작은 단위의 문제는 arrSum([]) 이었다. 빈 배열의 합은 0이므로 0을 반환해준다.

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;

arrSum 함수의 반환값을 구하면서 연쇄적으로 문제가 해결되고, 문제 전체가 해결되는 것을 볼 수 있다.

이것을 참고하여 arrSum 함수를 작성해보자.

funciton arrSum (arr) {
  // 빈 배열을 인자로 받았을 경우 0을 반환
  // base case : 가장 작은 단위의 문제 && 재귀를 멈추는 조건
  if(arr.length === 0) {
    return 0;
  }
  
  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 인자로 전달받는 arrSum()
  // recursive case : 자기 자신을 호출하는 재귀 함수
  return arr.shift() + arrSum(arr);