TIL 15일차

[자료구조/알고리즘] 재귀

재귀함수란?

• 재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.
• 자기자신을 호출하는 함수.

재귀함수의 장점:

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

재귀함수의 단점:

• 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵습니다.
• 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 됩니다. 이러한 과정은 반복문에 비해서 메모리를 더 많이 사용하게 되어 많은 메모리를 사용하게 됩니다.
• 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 됩니다.

재귀함수를 사용하기 위한 조건

• 문제를 작은 단위로 쪼개기 가능
• 호출이 종료되는 시점 존재

재귀함수 만들기

1. Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
2. Recursive Case : 그렇지 않은 경우

재귀함수 예시)

• case 1. 배열의 합 구하기
  - for문의 사용한 경우

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

  -재귀함수를 사용한 경우

      public int arrSum(int[] arr){
          //Base Case
          //arr의 길이가 0일때 0을 리턴
          if(arr.length == 0){
              return 0;
          }
  
          //Recursive Case
          //배열의 첫번째와 첫번째를 뺀 배열을 재귀호출
          int[] tail = Arrays.copyOfRange(arr, 1, arr.length);
          return arr[0] + arrSum(tail);
      }