21_재귀 함수_22.09.20

학습 목표

• 재귀 함수 개념 이해
• 재귀적 사고 연습

 

재귀 함수

>의미 및 특징

: 원래의 자리로 되돌아오는 함수

: 호출 시, 다시 본인(함수)을 호출하는 함수.

: 몸체에 본인을 호출하는 코드가 존재함

: 함수가 해결되면, 제일 마지막(내부)부터 제일 처음(외부)까지 거슬러 올라가면서 계산이 이루어짐.

>조건

• 문제를 더 작은 단위로 쪼갤 수 있어야함.
• 재귀 호출이 종료되는 시점을 설정해야함.

>장점

: 반복문을 사용하지 않음

: 코드가 간결하고 수정이 용이함(반복문 X)

: 변수의 양을 줄일 수 있음. (오류를 줄일 수 있음)

/*

22.10.19

변수의 양을 줄일 수 있는 장점 외에는 사실 명확한 장점은 아닌 것 같다.
하지만 재귀로만 풀 수 있는 문제들이 있고, 이를 분명하게 정리해두면 장점으로 표현할 수 있을 것 같다.

*/

>단점

: 코드의 흐름을 직관적으로 파악하기 힘듬.

: 반복문과 달리 매번 함수를 호출하여 문제를 해결하는 방식이기 때문에, 메모리 사용량이 많아짐(지역변수, 매개변수, 반환값 모두를 Process stack에 저장)

: 메서드가 종료된 이후 복귀를 위한 컨텍스트 스위칭 비용 발생

컨텍스트 스위칭
대기 상태와 실행 상태를 번갈아가며 하는 것 정도로 기억하자.

/*

22.10.19

재귀 함수는 메모리 사용량에 대한 단점이 가장 큰 문제이다.

이에 대해 재귀 함수를 최적화하려는 노력 중 하나가 꼬리 재귀이고, 꼬리 재귀는 조금 더 알아두자.

*/

>재귀로 풀기 유리한 상황

• 문제가 비슷한 구조의 더 작은 문제로 나눠지는 경우
• 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측하기 어려운 경우

// 하지만 실무(?)에서 대부분은 굳이 사용할 필요가 없다는 것 같다. 괜한 메모리 낭비가 발생하기 때문에.

// 그래도 꼭 필요한 이유도 있다. 그 중에 대표적인건 코딩 테스트! 재귀 함수로만 풀 수 있는 문제가 있을 것이라고 한다.

 

재귀적 사고 연습

1. 경우의 수 나누기

: 단순하게 풀 수 있는 경우들을 미리 해치운다. (Edge case)

2. head와 tail 나누기

head: 쪼개진 값(이미 쪼개진 값), 재귀 함수에서 벗어난 값

tail: 더 쪼갤 값, 재귀 함수로 돌릴 값

3. 재귀 함수 탈출 시점 지정

: tail의 재귀 함수가 탈출할 시점을 지정.

4. return 값 지정

: 재귀 함수의 특성상, return 을 어느 시점에서 하는 지에 따라 정말 기발하게 값을 구할 수 있다.

예시)

• 1. 재귀 함수 마지막에서 반환.

: 재귀 함수 종료 시점에서 반환하며, 굳이 다시 값을 되짚어가지 않게 된다.

• 2. 재귀 함수 종료 후 다른 지점에서 반환

: 재귀 함수가 종료 시점에서 종료 된 후, 값을 다시 되짚어가며 head 와 tail로 값을 만들어 반환한다.

// 말로 하면 진짜 어렵다. 코드를 보자

>예시

목표: 인자로 주어진 배열을 역순으로 변환시켜 반환하기.

//최종 반환이 재귀 함수 외에서 이루어진다.

public int[] reverseArr(int[] arr){
  if(arr.length==0) return new int[0]; // 탈출 조건
  int[] head = Arrays.copyOfRange(arr,arr.length-1,arr.length);
  int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length-1));
  int[] result = new int[head.length+tail.length];
  System.arraycopy(head, 0, result, 0, head.length);
  System.arraycopy(tail, 0, result, head.length, tail.length);
  return result;
}

 

//세상세상 어려웠다... 뒤늦게 이해했지만, 연습이 필요할 것 같다.

/*

22.10.19

재귀 함수는 이론적인 공부는 거의 의미가 없다.

무조건 문제로 익숙하게 만들고, 이론적인 부분은 깃헙을 참고해서 대답할 수 있을 정도만 정리하자.

*/