재귀함수

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

재귀 : 원래의 자리로 되돌아가거나 되돌아옴

---

🙋‍♂️ 언제써??

1. 주어진 문제를 비슷한 구조로 더 작게 쪼갤 수 있는 경우
2. 반복문의 중첩이 많을 경우
3. 많은 변수 사용으로 프로그램 오류 위험이 있는 mutable state(값이 변경 가능한 상태) 를 제거해야 할 경우

---

[재귀로 문제를 해결하기]

1. 문제를 가장 작은 단위까지 쪼갠다
2. 가장 작은 단위의 문제부터 해결함으로써 모든 문제를 해결

💻 예시

arrSum : 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 메서드
arr = [1, 2, 3, 4, 5]

arrSum([]) == 0; // (1) 문제가 더는 작아지지 않는 순간

// (2) 가장 작은 경우의 해결책을 적용, 그 순간 거꾸로 거슬러 올라가면서 합쳐지게 된다!

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;

이제 코드로 구현!

public int arrSum (int[] arr) {

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

  int[] tail = Arrays.copyOfRange(arr, 1, arr.length); // 나머지 요소 배열

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

🤚 .copyOfRange(배열명, 시작위치, 끝위치) : 범위를 지정하여 배열 복사

| 조건

• 문제의 크기를 점점 작게 쪼갤 수 있어야 한다
• 재귀 호출 종료 시점이 있어야 한다

---

| 장점

• 불필요하게 여러 반복문 사용 X ➜ 코드간결, 수정용이
• 변수를 여러 개 사용할 필요없음

| 단점

• 반복문과 달리, 코드의 흐름이 직관적이지 않음
• 메서드를 반복 호출하여 모두 process stack에 저장 ➜ 많은 메모리 사용
• 메서드 종료 후 복귀를 위한 컨텍스트 스위칭 비용이 발생

---

💛 재귀함수 이용 가이드 💛

1. 입력값과 출력값을 정의하라

arrSum : [int] -> int : 함수 arrSum 는 int 타입을 요소로 갖는 배열을 입력으로 받고, int 타입을 리턴

2. 문제를 쪼개고 경우의 수를 나누기

: 중요한 관점은 입력값이나 문제의 순서와 크기

arrSum: [number] => arrSum(new int[]{}) / arrSum(new int[]{e1, e2, .., en]} : ' 빈 배열인 경우와 / 그렇지 않은 경우 ' 로 나눌 수 있음
3. 단순한 문제부터 해결하기 : 재귀의 기초(base case)

재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성
arrSum: [number] => arrSum(new int[]{}) = 0 : 빈 배열의 리턴값 = 0

4. 남은 복잡한 문제 해결하기

< head : arr의 맨 앞 요소 / tail : 나머지 부분 (첫 요소만 제거된 배열) > 으로 구분하여 head 에 계속 추가5. 코드로 구현하기

5 . 코드 구현

public int arrSum(int[] arr) {
	//Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
	if (arr의 길이가 0인 경우) {
 	return 0;
	}
/*
* Recursive Case : 그렇지 않은 경우
* 문제를 더 이상 쪼갤 수 없는 경우
* head: 배열의 첫 요소
* tail: 배열의 첫 요소만 제거된 배열
*/
	return head + arrSum(tail);
}

---

💻 재귀함수 템플릿

  public type recursive(input1, input2, ...) {
     
  	// Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  	if (문제를 더 이상 쪼갤 수 없을 경우) {
    	return 단순한 문제의 해답;
  	}
     
  	// recursive Case : 그렇지 않은 경우
  	return 더 작은 문제로 새롭게 정의된 문제
     
 	 // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  	// 예2. someValue * recursive(input1Changed, input2Changed, ...)
  }