[자료구조/알고리즘] 재귀 함수 (Recursion Function)

1. 재귀함수의 개념

재귀함수 : 자기 자신을 호출하는 함수

2. 재귀함수의 필요성

반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있습니다.

3. 재귀함수를 작성하는 법

1) 문제를 작게 쪼갭니다. 2) 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갭니다. 3) 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결할 수 있습니다.

3 - 1. 예제 : 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 `arrSum` 을 작성

1) 문제를 작게 쪼갭니다.

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

2) 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]) === 5 + arrSum([])
arrSum([]) // 가장 작은 문제 단위

3) 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결할 수 있습니다.

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  // 	가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드 : Base case
  if (arr.length === 0) {
    return 0;
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  // 	재귀를 통해 문제를 작게 쪼개나가는 코드 : recursive case
	return arr.shift() + arrSum(arr);
}

※ 코드 해설

arrSum([]) 는 조건문에 의해 더이상 자기 자신을 호출하지 않고, 숫자 0을 리턴하면서 종료됩니다.
그 결과로 중첩되어 있던 함수들 또한 연쇄적으로 숫자를 리턴하게 되고,
최종적으로 배열의 모든 요소의 합을 리턴하며 문제가 해결됩니다.

 

※ 재귀함수 작성 방법에 대한 추가 설명이 필요한 경우 아래 링크 참고

2022.12.16 - [강의 요약/Chapter 3] - [자료구조/알고리즘] 재귀 함수 작성 가이드

4. 재귀함수 사용이 권장되는 상황

1) 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 2) 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우 ✔

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있습니다.

그러나 재귀를 적용할 수 있는 대부분의 경우, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.

 

(※ 이 밖에도, 재귀는 알고리즘 문제의 많은 부분을 차지하기 때문에 기초를 확실하게 다져두는 것을 권장합니다.)

5. 학습 후 내린 주관적 결론

재귀함수는 자기 자신을 호출하는 함수이다. 이러한 특성을 이용해 같은 구조가 반복되는 형태를 가진 복잡한 반복문을 재귀함수를 이용하여 간결하게 표현할 수 있다.

※ 반복문으로 해결할 수 있는 문제의 형태를 분석하여, 재귀를 적용할 수 있다면 재귀함수를 활용하는 구조로 코드를 바꾸는 연습 해보기