재귀함수란?

재귀

재귀란 원래의 자리로 돌아오다라는 뜻을 가지고 있다.

재귀함수를 사용하는 이유는 불필요한 반복문들이 필요없고 코드의 간결성과 수정의 용이함이다. 또한 여러개의 변수를 사용할 필요도 없다.

그러나 반복문과 달리 코드흐름을 직관적으로 파악하기 어렵고 자기 자신을 계속 호출하는 재귀함수는 stack메모리영역에 저장되어 메모리 사용이 크다는 단점이 있다. 또한 메서드가 종료된 이후에도 복귀하기 위한 컨텍스트 스위칭비용이 발생한다.

재귀함수를 사용하기 위해서는 문제의 크기를 작은 단위로 쪼갤 수 있어야 하며 호출이 종료되는 시점이 반드시 존재해야한다.

재귀로 문제를 해결하는 3단계
1. 문제를 작게 쪼갠다.
2. 문제가 더 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 해결하면 전체문제를 해결할 수 있다.

재귀함수의 예

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

예를 들어 배열arr에 모든 요소를 더해준다는 메서드가 있다.
위와같이 반복문으로 해당문제를 해결하는 방법이 있지만 재귀적으로 생각하여 문제를 해결해보자

1. 문제를 작게 쪼갠다.

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

arr의 요소를 더하는 과정은 [1,2,3,4,5]의 합을 구하는 것보다 [2,3,4,5]의 합을 구하는 것이 더 작은 문제가 될 것이다.

2. 문제를 가장 작은 단위로 쪼갠다.

문제를 더이상 쪼갤 수 없는 상태에 도달하게 한다. 빈배열이 될 때까지 쪼개었다.

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

3. 문제 해결

가장 작은 단위의 문제부터 해결한다. 이것은 문제 전체를 해결할 수 있도록 해준다.
arrSum의 메서드의 가장 작은 문제는 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; //리턴값 15

이러한 방식은 arrSum()의 리턴값을 해결 할 수 있게 해준다.

public int arrSum (int[] arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  if (arr.length == 0) {
    return 0;
  }

  int[] tail = Arrays.copyOfRange(arr, 1, arr.length);
  //Arrays.copyOfRange(원본 배열, 복사할 시작인덱스, 복사할 끝인덱스) 인덱스는 0부터 시작하는것 기준

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  // --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr[0] + arrSum(tail);
}

---

✍🏻 이럴 때 재귀함수를 사용하세요

for문의 for문의 for문의 .. for문의....!!!

for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
		for(int k = 0; k < n; k++) {
			for(int l = 0; l < n; l++) {
				for(int m = 0; m < n; m++) {
					// do something
					someFunc(i, j, k, l, m);
				}
			}
		}
	}
}

⭐️ 재귀함수의 유용성!

---

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 쪼갤 수 있다면
2. 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어렵다면
3. 변수사용을 줄여 프로그램 오류가 발생할 수 있는 가능성을 줄이고 싶다면