재귀

재귀함수 풀이 기본 구성

• Base Case : 문제를 더 이상 쪼갤 수 없는 경우
• Recursive Case : 그렇지 않은 경우
  

ex) 
public int arrSum(int[] arr) {
  //Base Case
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  // Recursive Case
  head, tail 정의
  return head + arrSum(tail);
}

  * head: 가장 작은 단위로 쪼갠 첫 요소
  * tail: 나머지 요소 (다시 재귀함수에 넣어 쪼갠다)

재귀함수의 장단점 (반복문과 비교)

• 장점
  - 반복문보다 코드가 간결하고, 수정이 용이하다.
  - 변수를 여러개 사용할 필요가 없다.
• 단점
  - 재귀함수가 함수를 호출할 때마다 콜스택에 함수의 매개변수,지역변수,반환주소값 을 모두 저장하기 때문에 반복문보다 메모리의 사용량이 더 많다.
  - 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 된다.

회고

재귀함수가 반복문보다 메모리의 사용량이 더 많기 때문에 많이 쓰는 방식은 아니지만, 필요시 사용 가능할 수 있도록 반복 연습이 필요할 것 같다.

• 문제를 풀이/재귀구현 과제 후기
  계속 문제를 쪼개다가(Recursive Case), 더 이상 쪼갤 수 없는 경우(Base Case)를 만났을 때, 쪼개졌던 것들을 거꾸로 거슬러 올라가면서 합쳐가며 계산하는 과정을 잘 이해하고 코드를 만들어야 한다.
  코드 자체가 길고 복잡하지 않은데도, 어떤 식으로 구현해야되는지를 헤매는 데에 긴 시간을 소비했다. 테스트 케이스를 중간중간 실행해보며 맞는 방향인지, 어디서 문제가 생기는지 확인하며 만들어 나간게 도움이 되었다.