11.17 재귀

오늘부터 section2가 시작되었다. 새롭게 알고리즘 푸는시간이 생겼다. 첫문제는 배열을 입력받아 첫요소와 마지막 요소로 키와 값 으로 받는 Hashmap을 리턴하는 문제였다. 빈 해시맵 객체를 선언하고 거기에 put()으로 값을 넣었다. 연습문제 풀었던걸 복습해 가며 다시 풀어봐야겠다.

 

ㅇ 재귀

원래의자리로 되돌아가거나 되돌아온다는 의미.

처음에 이게 무슨 소린가했는데 코드를 보니 이해가 어느정도 갔다.

public void recursion(){
    System.out.println("this is");
    System.out.println("recursion");
    recursion();

이런식으로 메서드내에 자신을 집어넣는 구조를 말한다.

하지만 이렇게되면 무한루프가 발생되므로 꼭 빠져나올 수 있는 코드를 넣어야 한다.

 

ㅇ 재귀적인 사고

먼저, 입출력값을 정의하고 문제를 쪼개고 경우의 수를 나눈다. 그리고 단순한 문제부터 복잡한문제 순서로 해결한다.

처음에 문제를 쪼갠다했을때 이해가 전혀 가지 않았는데, 페어와 함께 연습문제를 풀다보니 이해가 갔다.

public int factorial(int n){
if(n == 0) return 1;
return n * factorial(n-1);
}

팩토리얼문제를 풀 때, n이 만약 5라했을때,

return 문을 보면

5 * factorial(4)가 되고이것을 다시 쪼개면

5 * 4 * factorial(3)이 되며 점점점 쪼개지면서

. . . .

5 * 4 * 3 * 2 * 1 이 된다.

 

ㅇ 헤드 테일 이용

public int arrSum(int[] arr){
if(arr.length == 0) return 0;

int head = arr[0];
int[] tail = Arrays.copyOfRange(arr, 1, arr.length);
return head + arrSum(tail);
}

또, 이렇게 첫요소를 head로 잡고 그외의 나머지요소를 tail로 잡고 또 테일에서 첫요소를 뺀 나머지를 계속해서 더해주는 과정을 작성해 보니, 이해가 갔다.