코드스테이츠 수강_6주차_2~3일차_재귀함수

코드스테이츠 수강 6주차 2일차에는 재귀함수에 대해 배웟다.

재귀함수

재귀함수, 이름만 보면 재귀? -> 반복? -> 돌아온다고?

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

잉? 뭔 말이냐고? 

먼제, 쉬운 비유를 의해 뱀 한마리를 등장시키겟다.

비얌이에여유

뱀은 어떤식으로 생겼는가? 원래 제멋대로 생기긴 했지만 일단

머리에서 뻗어나온 몸통, 그리고 꼬리로 이루어져 있다. 

머리 방향으로 돌아댕기는 뱀

뱀은 움직일 때 머리 방향으로 꿈틀꿈틀 겨댕기는데, 머리 - 몸통 - 꼬리 순으로 꿀렁꿀렁 기어간다. 

이때, 뱀을 메서드로 대입하면 

머리 : 메서드 헤드부분 

몸통 : 메서드 바디부분

꼬리 : 메서드 끝부분(?)

으로 볼 수 있다. 

뱀이 기어간다. = 메서드가 실행된다. 라고 생각하자

그런데 만약 뱀이 신나게 기어가다가 유턴해서 자신의 꼬리쪽으로 달려가면 

오?

위와같이 꼬리가 입에 만나게 된다. 

 

이때 우리가 봣을 때 머리 - 몸통 - 꼬리 - 머리 - 몸통 - 꼬리 처럼 보인다. 

메서드로 치면 메서드 헤드 -> 바디 -> 끝부분 - >헤드 -> 바디 -> 끝부분으로 계속 반복되는것 처럼 보인다. 

어...어...?

위의 그림처럼 마치 어디서 많이 본듯한 형태가 된다. 

결론적으로 요약하면, "자기 자신을 반복해서 실행하는 함수가 된다." 는 것이다. 

 

재밌는 사실 : 케쿨러라는 화학자가 있는데 이양반이 꿈에서 뱀이 자기 자신의 꼬리를 물고 있는걸 보고 벤젠의 화학식을 떠올렷다고 한다. 그게 위의 뱀 짤이다.

 

코드 예시

public void recursion() {
  System.out.println("시공의 폭풍은");
  System.out.println("정말 최고야!!");
  recursion();
}

//출력
시공의 폭풍은
정말 최고야!!
시공의 폭풍은
정말 최고야!!
시공의 폭풍은
정말 최고야!!
시공의 폭풍은
정말 최고야!!
.......

위의 코드와 같이 메서드를 메서드 내용 중 끝부분에 넣으면, 다시 그 메서드가 호출되고 그메서드가 또... 계속 된다.

물론, while, for문으로 위의 동작을 똑같이 만들어 줄 수 있다. 

하지만 재귀"함수" 이기 때문에 장점이 있다. 

1. 불필요하게 여러개 반복문을 사용하지 않기 때문에 코드가 간결해지고 수정이 용이하다. 
   
   
2. 변수를 여러개 사용할 필요가 없다. 
   
   
3. 함수의 매개변수, 지역변수, 반환값도 모두 반복하기 때문에 일일히 만들어 줄 필요가 없다!
   (-중요, 단순작업뿐아니라 매개변수 등을 받아서 복잡한 기능을 하는 경우에는 재귀함수로 함수 자체를 반복하는 것이다.)

물론 단점도 있다.

1. 코드의 흐름을 직관적으로 파악하기 힘듦
   (그냥 쭉 읽는게 아니고, 왜 이렇게 동작하는지 생각해야함 ,위의 장점으로 복잡한 기능을 반복한다고 했는데, 이거는 복잡한 기능을 생각해야함)
   
   
2. 반복하여 메서드를 호출하게 되면 지역변수, 매개변수, 반환값을 모두 스텍메모리에 저장하면서 사용하는데, 한번 호출할때마나 메모리 사용량이 메서드 크기만큼 늘어난다는 것이다. 
   (메모리 사용량 증가)
   
   
3. 메서드를 호출하고 메서드가 종료된 이후 복귀를 위한 컨텍스트 스위칭이 필요 

재귀함수를 사용하려면 조건도 필요하다. 

1. 문제(내부 실행되는 부분)을 작은 단위로 쪼갤 수 있어야 한다.
   
   
2. 재귀 호출이 종료되는 시점이 존재해야 한다.(중요)

재귀함수를 잘 나타내는 짤이 또 있는데, 바로 강아지 꼬리물기 짤

 

빙글빙글

강아지가 자신의 꼬리를 따라 빙빙 도는 걸 영상이든 어디든 접한 경험이 있을 것이다.

이 짤의 강아지를 보면 빙빙 돌다가, 멈춘다.

스스로 지쳐서 멈추거나, 주인이 그만이라고 해야 멈추거나 

조건이 필수적으로 필요한 것이다.

그렇지 않으면 위에서 말한것 처럼 스택 메모리에 함수가 차곡차곡 쌓여서 무한히 증식하게 되는데, (안멈추고 계속 돌면)이때 스택오버플로우 오류가 나게된다. 
(재귀함수를 쓰는데 스택오버플로우  오류가 나면, 이 조건을 설정을 잘 못한것이다. )

 

재귀함수 사용

재귀함수를 사용할 때 그냥 for문, while문 쓰듯이 쓰면 생각보다 잘 안된다.

문제는 작동방식의 차이가 있기 때문이다. 

예를 들어 "자연수로 이루어진 배열을 입력 받고 그 안의 요소들을 합하는 코드를 작성해라" 라고 한다면 

우리는 당연하게 이렇게 쓸 것이다.

코드 예시

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

그런데, 이 코드를 재귀함수로 만드려면 어떻게 할까?

위에서 말한 재귀함수 사용 조건대로 

1. 문제를 작게 쪼갠다.
   
   
2. 문제가 더 작아지지 않는 최소단위로 계속 쪼갠다. 
   
   
3. 최소단위의 문제를 해결 -> 다음단계 해결됨 -> 해결됨 -> 해결됨 .... 

일단 위의 코드에 [1, 2, 3, 4, 5 ]를 대입했다고 가정하자. 

그러면 이걸 쪼갠다고 보면 

먼저 첫번째 숫자 1 , 두번째 숫자 2를 더해서 3 이 나오고

더해진 3에 세번째 숫자 3을 더해서 6이 나오고 

더해진 6에 네번째 숫자 4를 더해서 10이 나오고

더해진 10에 다섯번째 숫자 5를 더해서 15가 나오게 된다. -> 정답 15 

코드로 나타내면 

arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5])
arrSum([3, 4, 5]) == 3 + arrSum([4, 5])
arrSum([4, 5]) == 4 + arrSum([5])
arrSum([5]) == 5 + arrSum([])

그런데, 가장 작게 쪼개진것이 무엇인가? 

가장 아래의 arrSum([5]) == 5 + arrSum([]) 인 것이다. 

이 부분을 해결하고, 위의 코드를, 또 위의 코드를 해결 한다고 생각하면 된다.

반대로, 코드는 위에서 아래로 작동한다. 

그러면 작은거부터 해결하면

arrSum([]) == 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용
arrSum([5]) == 5 + arrSum([]) == 5 + 0 == 5;
arrSum([4, 5]) == 4 + arrSum([5]) == 4 + 5 == 9;
arrSum([3, 4, 5]) == 3 + arrSum([4, 5]) == 3 + 9 == 12;
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5]) == 2 + 12 == 14;
arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5]) == 1 + 14 == 15;

위와같이 된다. 

가장 작은 빈 배열 = 0 

5를 가진 배열 = 5

4 ,5 를 가진 배열 = 9 

3, 4, 5를 가진 배열 =12

2, 3, 4, 5 를 가진 배열 = 14

1, 2, 3, 4, 5를 가진 배열 = 15

이를 재귀함수로 나타내면

public int arrSum (int[] arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length == 0) {
    return 0;
  }

  int[] tail = Arrays.copyOfRange(arr, 1, arr.length);

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr[0] + arrSum(tail);
}

들어온 배열을 앞자리만 두고 뒤을 요소들을 복사해서 다음 함수에 넣는다. 

텍스트로 표현하면 이렇다. (1~5까지를 예를 들면)

[1, 2, 3, 4, 5] 입력됨 

[1] + 재귀함수([2, 3, 4, 5]입력, 2 출력 , 재귀함수([3, 4, 5]입력, 3 출력 , 재귀함수([ 4, 5]입력, 4 출력 ,재귀함수([5]입력, 5 출력 ,재귀함수([]입력, 0 출력 ))))

와 같아진다. 

우리가 스택 메모리라고 하지 않았는가?

그래서 가장 늦게 넣은 부분이 가장 먼저 실행된다.

고로, 가장 작게 쪼개진 부분에서부터 (뒤에서 부터) 가장 큰 부분으로 (앞으로) 계산된다. 

이 글을 읽고, 아래의 짤을 보면 바로 이해된다.

 

먼저 

재귀로 문제가 쪼개지는 과정

[1, 2, 3, 4, 5] 에서 한 요소씩 줄어들면서 쪼개지는 모습 (출처 : 코드스테이츠)

배열의 한 요소씩 쪼개서 재귀함수를 만드는 과정 

재귀로 문제가 해결되는 과정

빈 배열 []에서 한 요소씩 더해지면서 해결되는 모습 (출처 : 코드스테이츠)

메서드가 호출 될 땐, 배열의 값을 하나식 리턴하면서 불려지다가 0을 리턴하면서 종료되지만, (문제가 쪼개짐)

종료 되면서 스택 메모리에 있던 함수들이 나오면서 (늦게 들어간 순으로, 0부터 5까지 나오면서) 더해지게 된다.

 

재귀적으로 사고하기

for문으로 쓰면 그냥 선형적으로 1+2+3+4+5 하면 되는데 이게 뭔 고생이냐? 할 수있다.

하지만 ,앞서 말한것 처럼 복잡한 기능을  반복할 때 재귀함수가 적절하기 때문에 재귀함수를 써야한다.
(찾아보니, 트리구조, 깊이 우선 탐색, 넓이 우선 탐색 등의 코테 유형에 사용되니 알아야 한다. ㅠㅠ)

처음 for문 배울때도 뭐가뭔지 몰랏지 않은가? 

재귀함수도 사용하는데 익숙해지면 사용하기 쉬워진다. 

 

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

위의 코드에서 출력값은 그대로 나오는데, 재귀함수에 다시 입력값을 넣어서 연산하게 했다. 

이거를 잘 정해야 한다. 

대강, 우리가 int 배열을 넣엇는데, int 출력을 내놓으니 

arrSum: [int] -> int

이라고 할 수 있겠다.

 

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

아까, 배열을 하나하나 쪼갰는데, 이때 두가지 경우가 있었다. 

arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5])
arrSum([3, 4, 5]) == 3 + arrSum([4, 5])
arrSum([4, 5]) == 4 + arrSum([5])

처럼, 쪼갠 것들을 연산 할 수 있는 경우와 

arrSum([5]) == 5 + arrSum([])

더이상 못 쪼개는 경우가 나뉘는 것이다. 

고로,

arrSum: [number] => arrSum(new int[]{}) / arrSum(new int[]{e1, e2, ... , en]}

처럼 나타낼 수 있다. 

 

3. 단순한 문제 해결하기 

문제를 쪼갠 후, 가장 해결하기 쉬운거부터 해결하는데 이를 재귀의 기초(base case)라고 한다. 

이 재귀의 기초는 나중에 재귀함수의 탈출조건(강아지가 빙빙 돌다가 멈추는 조건)이 된다.

함수를 더 쪼갤 수 없을 때는 arrSum(new int[]{}의 리턴값은 0 이 나온다.

고로

 arrSum : [number] => arrSum(new int[]{}) = 0 / arrSum(new int[]{e1, e2 , .... ,en]}

처럼 나타낼 수 있다.

4. 복잡한 문제 해결하기 

길이가 1 이상의 배열이 들어오면, 맨 앞의 요소를 빼내고, 뒤에있는 요소를 또 재귀에 넣고, 또 떼고... 를 반복한다. 

이때 맨 앞의 요소를 빼낸거를 head라고 하고 , 나머지 요소를 넣는것을 tail이라고 하겟다. 

arrSum: [number] => numberarrSum(new int[]{}) = 0 / arrSum([e1, e2, ... , en]) = arrSum(new int[]{e1} + arrSum(new int[]{e2, ..., en]}

으로 나타낼 수 있다.

위의 수식을 보니까 더 모르겠다고? 

그러면 보지 않아도 된다. 

그저 "재귀함수를 쓸때는 문제를 쪼개서, 한단계 한단계 해결하고, 특정 조건이 되면 끝나게 설정한다." 가 핵심이다.

 

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, ...)
}

 

 

 

 

간만에 다시 좀 내 방식으로 비유를 많이 써서 포스팅을 햇다

그나마 범위가 좁고, 컨디션도 좋아서 이렇게 쓴거같다.

백준 단계별 풀어보기로 독학하면서 하면 잘 안됫는데, 이런 코드 양식이 비슷하게 있는것을 알았으면 더 좋았겠구나 한다.

다행히 부스트캠프가 독학보다 나은것 같다.

다행이다.