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

재귀함수란

우선 재귀란 사전적 의미는 무엇인가?

"원래 자리로 돌아오다" 이다.

프로그래밍 세계에서는 메소드가 자기자신을 다시 호출 하는것에 해당한다.

 

재귀의장점

• 코드의 간결화
  반복적인 처리를 재귀로 처리하므로 반복문에 비해 코드가 간결해진다.
  
  
• 필요한 변수의 수가 줄어든다.
  재귀가 아닐 경우 반복문에 사용되는 변수들만하여도 이미 재귀를 사용할때에 비해 많다.
  
  

재귀의 단점

• 코드의 흐름을 순차적으로 따라가면 확인하기가 어렵다.
• 메소드를 반복하여 호출하므로 지역변수, 매개변수, 리턴값을 모두 process stack에 저장한다.
  이러한 이유 때문에 반복문 사용때보다 더 많은 메모리를 사용을 하게된다.
  
  
• 호출한 메소드가 종료될때마다 컨텍스트 스위칭 처리 비용이 발생한다.
  그러므로 총 처리시간도 반복문으로 처리하는것이 더 빠르다. 
  
  

재귀 함수를 사용할 수 있는 조건

• 문제의 크기를 점점 작은 크기로 쪼갤 수 있어야함.
  
  이 부분은 기능들을 하나하나를 메소드로 쪼개는 객체지향의 관점 보다는 입력되는 인풋값 자체를 동일한 로직으로 쪼갤 수 있는가에 대한 고민을 해봐야 하는점 같다.
  
  EX : 
  문제 : 1 ~ 4까지 더해라.
  1 + f(배열 2 ~ 4) 
  -> 1 + 2 + f(배열 3~4)
  -> 1 + 2 + 3 + f(배열4)
  
  위와 같이 동일한 f() 로 (메소드)  인풋 잘게 쪼개어 전달해서 해결이 가능한 문제인가!
  
  
• 재귀 호출의 종료 조건(시점)이 존재해야 한다.
  인풋을 잘게잘게 쪼개서 결국 더 이상 쪼갤 수 없는 순간이 존재하는가!
  
  위와 같은 경우에 f(배열 4) 는 인풋값을 더 이상 쪼갤 수가 없다. 배열의 요소가 1개이기 때문이다.
  그러므로 이 순간 값 자체를 리턴하는 조건을 넣어줘서 이전 호출됬던 메소드들을 연속적으로 종료시켜 값을 얻을 수 있다
  
  

재귀의 문제 해결 방법

다음은 문제를 해결하는 방법의 원리이다.
1~3까지 더하는 메소드를 재귀로 구현한다고 생각해보자.

1. 문제를 잘게 쪼갠다
   
   arrSum(1,2,3) 은 1 + arrSum(2,3) 과 동일.
   1 + arrSum(2,3) 은 1 + 2 + arrSum(3) 과 동일
   
   
2. 1번에서 쪼개진 문제(인풋)가 더이상 쪼개 질 수 없는 상황이 됬을때, 그 가장 작게 쪼개진 단위의 문제를 해결한다.
   
   arrSum(3) 은 요소가 3 한개이기 때문에 그냥 요소 3을 리턴해주면 된다.
   그럼 호출됬던 메소드들에 연쇄적으로 리턴을 하게 되며 원하는 값을 얻게 된다.
   arrSum(3) 은 3이므로
   1 + 2 + 3 이 된다.
   
   
   
   

재귀적 사고 연습하기

1. 재귀 함수의 입력값과 출력값 정의하기.
   
   문제를 가장 추상적으로 또는 단순하게 정의를 내릴 수 있어야한다
   
   
2. 문제를 어떻게 쪼갤 것인가 파악
   
   인풋을 기준으로 쪼갠다면,
   인풋을 쪼개고 쪼개서 결국,
   더 이상 쪼갤 수 없는 상황과 더 쪼개질 수 있는 상황이 있을 수 있겠다.
3. 단순한 문제 해결하기
   
   문제를 쪼갠뒤 더 이상 쪼개 질 수 없는 가장 작은 단위의 문제를 해결한다.
4. 복잡한 문제 해결하기
   
   길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 더합니다.
   arrSum: [number] => numberarrSum(new int[]{}) = 0 / arrSum([e1, e2, ... , en]) = arrSum(new int[]{e1} + arrSum(new int[]{e2, ..., en]}
   배열을 head와 나머지 부분(tail)으로 구분하는 방법만 안다면, 함수 arrSum을 재귀적으로 구현할 수 있습니다.
   
   
   
5.  코드 구현

public int arrSum(int[] arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}

아래는 일반적인 재귀 함수의 템플릿입니다. 재귀 함수 연습에 활용하세요.

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