목차

---

1. 재귀 개념
2. 재귀함수

배운 내용

---

재귀(Recursion)

• 원래의 자리로 되돌아가거나 되돌아옴.
• 자기 자신을 끝없이 호출하면서 같은 코드가 반복해서 실행된다.

재귀함수

• 자기 자시을 호출하는 함수

장점

• 불필요하게 여러개의 반복문을 사용하지 않기 때문에, 코드가 간결해지고, 수정이 용이
• 변수를 여러개 사용할 필요가 없다.

단점

• 코드의 흐름을 직관적으로 파악하기 어려움
• 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장 →많은 메모리 사용
  
• 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생

사용조건

• 문제의 크기를 점점 작은 단위로 쪼갤수 있어야 한다.
• 재귀 호출이 종료되는 시점이 존재해야한다.

재귀를 통한 문제 해결

1. 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
2. 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결한다.

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 메서드의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결

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

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

재귀를 사용하기 적합한 상황

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

**재귀적 사고**

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
3. 단순한 문제(재귀의 기초) 해결하기

• 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성

1. 복잡한 문제 해결하기

//재귀 일반 템플릿
* head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
 return head + arrSum(tail);
  */
 

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

//입력받은 배열의 모든 요소의 합 리턴
public int arrSum(int[] arr){
    //TODO.. 
  if(arr.length == 0) return 0;
  if(arr.length == 1) return arr[0];

  return arr[arr.length -1] + arrSum(Arrays.copyOf(arr, arr.length -1));

  }
// 차례대로 num개의 요소가 제거된 새로운배열리턴
public int[] drop(int num, int[] arr){
    // TODO:
    if(num == 0 || arr.length==0) return arr;
    
    return drop(--num, Arrays.copyOfRange(arr, 1 ,arr.length));

	}

어려운 내용(에러)

---

객체 복사

깊은복사

• 객체의 실제값을 새로운 객체( 새로운 메모리 공간)로 복사하는것
• 복사된 배열이나 원본배열이 변경될 때 서로 간의 값은 바뀌지 않습니다.

// 반복문 사용한 깊은복사
public class Array_Copy{
public static void main(String[] args)  {
int[] a = { 1, 2, 3, 4 };
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = a[i];
}
}
}

**Object.clone()**

public class Array_Copy{
public static void main(String[] args)  {
int[] a = { 1, 2, 3, 4 };
int[] b = a.clone();
}
}
// 객체 배열의 경우 깊은복사가 안됨 , 객체는 주소값을 가지고 있기때문

**Arrays.copyOf()**

import java.util.Arrays;
public class Array_Copy{
public static void main(String[] args)  {
int[] a = { 1, 2, 3, 4 };
int[] b = Arrays.copyOf(a, a.length);
	}
}
// Arrays.copyOf(원본배열, 복사할길이) 

**Arrays.copyOfRange()**

import java.util.Arrays;
public class Array_Copy{
public static void main(String[] args)  {
int[] a = { 1, 2, 3, 4 };
int[] b = Arrays.copyOfRange(a, 1, 3);
}
}
//Arrays.copyOfRange(원본배열, 복사할 시작인덱스, 복사할 끝 인덱스)

**System.arraycopy()**

public class Array_Copy{
public static void main(String[] args)  {
int[] a = { 1, 2, 3, 4 };
int[] b = new int[a.length];
System.arraycopy(a, 0, b, 0, a.length);
}
}
System.arraycopy(원본배열, 원본시작점,새배열,새 배열시작점, 길이)

얕은복사

• 단순히 객체의 주소값만을 복사하는것
• 여러객체가 같은 주소를 참조하기 때문에 하나의 값을 변경해버리면 다른 대상의 값 또한 바뀐다.

public class Array_Copy{
public static void main(String[] args)  {
int[] a = { 1, 2, 3, 4 };
int[] b = a;
}
}
// '=' 연산자는 주소를 이어준다는 의미

2차원배열 복사

얕은 복사

• 단순 변수 선언 뿐만 아니라 A.clone()을 사용해도 얕은 복사가 됨.

깊은 복사

• 2중 반복문을 사용하여 가능
• 반복문 + System.arraycopy()를 사용하여 가능