드디어 한달이 지났다 !
짝짝짝 👏👏👏

image

섹션1이 끝나고 섹션2가 시작되는 날이다.
이제 조금 긴장이 되는 느낌?
여태까지 정말 기본인 자바문법과 사용방법들을
익혔다면, 이제 이것을 토대로 백엔드 파트에
들어가려고한는 단계이다.

크게 달라진점은 데일리 코딩이라는 시간이 생겼다.
아침 1시간마다 코딩문제 하나씩 푸는 시간을 가지는 과정이다.
매우 만족스러운 시간이라고 생가한다ㅎㅎ
이제 본격적으로 공부를 시작해보자!

오늘은 재귀에 대해 배워볼 예정이다.
예전에 잠깐 독학하다가 봤을대 많이 난해했던 기억이있다.
오늘 개념을 확실히 잡고가보자

재귀

재귀란? 말 그대로 직영하자면 “원래의 자리로 되돌아가거나 되돌아옴”
이라는 뜻을 가지고 있다. 반목문과 비슷하다고 생각하면
이해하기가 쉬울 것 같다.

간단한 예제를 보자

public void example(){
    System.out.println("재귀함수입니다.");
    example();
}
//출력
재귀함수입니다.
재귀함수입니다.
재귀함수입니다.
재귀함수입니다.
재귀함수입니다.
.
.
.
.

위와 같은 메서드를 보자
메서드 안에서 자기자신의 메서드를 계속해서 호출하고 있다.
어디선가 example();이라는 메서드를 호출하면
끝나지않는 무한루프에 빠진다.
이러한 원리라 기본적으로 생각하고 다음스텝을 넘어가보자

재귀함수의 장점
1). 불필요한 여러개의 반복문을 사용하지 않아, 코드가 간결해지고, 수정이 용이하다.
2). 변수를 여러개 사용할 필요가 없다.

재귀함수의 단점
1). 반복문과 달리 직관적으로 파악하기 쉽지않다.
2). 반복하여 메서드를 호출하며 지역변수,매개변수,반환값을 모두 stack에 저장하게된다.
이러한 과정은 반복문에 비해서 메모리를 더 많이 사용하게 된다.
3). 메서드를 호출하고 메서드가 종료된 이후 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.

재귀함수를 사용하기 위한조건
1). 문제의 크기를 작은단위로 쪼갤 수 있어야한다.
2). 재귀 호출이 종료되는 시점이 반드시 존재해야한다.

위에 대한 내용중 바로 이해되는 부분도있고
이해가 조금 어려운 부분도 있다.
이후에 조금더 공부해보자.

어떠한 수의 팩토리얼(factorial)값을 구한다고 생각해보자
팩토리얼이란 값이 5가 주어진다면 (1*2*3*4*5)= 120
이라는 값을 반환해주는 알고리즘이다.
for문과 재귀함수를 비교해보자

for 문으로 작성

public static void main(String[] args) {
    int num = 5;
    int result = 1;
    for(int i=1;i<=num;i++){
        result *= i;
    }
    System.out.println(result);
}
//출력
120

위와같이 반복문을 이용해 간단하게 작성할 수 있다.
증가되는 i값을 result의 계속해서 곱해주는 방식이다.

재귀함수를 이용해 작성

public class test {
    public static void main(String[] args) {
        test example = new test();
        System.out.println(example.factorial(5));
    }

    public int factorial(int num){
        // 재귀의 탈출조건 , 재귀의 기초(base case)를 구성한다.
        if(num==1) return 1;

        //문제를 쪼개고 경우의 수를 재귀함수로 구현하기
        return num * factorial(num-1);
    }
}
//출력
120

이렇게 작성할 수 있다.
위의 for문과 확연한 차이가 있다.
for문은 i와 result라는 변수가 선언되었는데
변수가 없이도 재귀함수를 이용해 같은 출력이 확인이 가능하다.
여기서 중요한 것이 쪼개고 경우의 수를 먼저 수도코드로 작성해보는게 좋다.
처음에 num = 5 라는 것을 가정해 한번 쪼개서 들어가보자.

위에서 아래순으로 작게작게 만든 수도코드다.
5팩토리얼을 위해서는 1~5까지 곱해야 값이 나온다
여기서 1~4까지 다시 팩토리얼로 묶어서 생각해볼 수 있다.
이렇게 끝까지 가면
마지막 최종적으로 1까지 도달하면

factorial(5) = 5 * (4 * 3 * 2 * 1)
factorial(4) = 4 * (3 * 2 * 1)
factorial(3) = 3 * (2 * 1)
factorial(2) = 2 * (1)
factorial(1) = 1

위에서 아래순으로 작게작게 만든 수도코드다.
이렇게 값이 진행되어야하고

아래와 같이 표현해보자

factorial(5) = 5 * factorial(5-1)
factorial(4) = 4 * factorial(4-1)
factorial(3) = 3 * factorial(3-1)
factorial(2) = 2 * factorial(2-1)
factorial(1) = 1 // 재귀함수 종료

5 * factorial(4)
-> 4 * factorial(3)
-> 3 * factorial(2)
-> 2 * factorial(1)
-> 1;

5 * (4 * 3 * 2 * 1)
-> 4 * (3 * 2 * 1)
-> 3 * (2 * 1)
-> 2 * 1
-> 1;

이렇게 재귀함수를 호출을 계속하다가 마지막 종료 num=1일 경우 재귀를종료해 값을 리턴하여
실행되었던 재귀함수들이 연쇄적으로 리턴하게되어
최종적으로 5*4*3*2*1 = 120이 출력되게 되어지는 것이다.
이렇게 간단한 예제로만 보면 사실 이해하기가 간단하다.

하지만 조금더 나아가 문제를 응용하게되면
멍~ 때리게된다. 어떻게 풀어야할지 난해한건 아직도 마찬가지지만
재귀는 계속계속 문제를 풀어보면서 적응을 해보는 수 밖에 없는 것 같다.

오늘은 재귀에 대한 문제를 12문제 정도 풀어보았다.
다 비슷한 예제의 문제들로 준비되어있었고
몇 문제 빼고는 이해가 어렵지는 않았다.

하지만 문제가 어려워질 수록
내가 재귀에 대해 이해를 하지 못했다는게 느껴지고
이걸 어떻게 하면 이해하면서 사용할 수 있을지
연구하기위해 오늘은 TIL작성 시간을 조금 줄여보고
문제 푸는연습을 더해보려한다.
오늘 공부는 여기서 끝!!


오늘의 커피량: ☕️ ☕️ ☕️ ☕️️️️
오늘의 점심: 떡볶이