[알고리즘]재귀

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

[재귀적 사고]

1. 재귀함수의 입력값, 출력값 정의

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

3. 단순한 문제 해결하기
   (이 때, 재귀의 기초. 즉, 재귀의 탈출조건을 구성한다.)

4. 복잡한 문제 해결하기

   아래의 예시로 재귀를 살표보면

//예를 들어  arr = [1,2,3]이라 가정
public int sum(int[] arr){
   if(arr.length == 0) return 0;
   
   int[] newArr = Arrays.copyOfRange(arr,1,arr.length);
   return arr[0] + sum(newArr)  // 1 + 2 + ......
}

위에서 sum(newArr)을 통해 자기 자신을 계속 호출하고 있다.
후에 재귀의 탈출조건을 통해 종료된다.

[재귀의 장점]

• 반복문을 대신하여, 코드가 간결해짐
• 변수를 여러개 사용할 필요가 없음

[재귀의 단점]

• 코드를 직관적으로 파악하기 어려움
• 메모리를 많이 사용하여 overflow를 유발함
• 메서드 종료 이후 복귀 위한 스위칭 비용이 발생