[Java] 반복 함수, 재귀 함수

[Java] 반복 함수, 재귀 함수

 

반복 또는 재귀 함수는 DP, DFS, BFS 등의 알고리즘에서 흔히 쓰이는 함수이다.

수학적 감각이 약간 필요한 친구라고 할 수 있겠다.

자기 자신을 또 호출하는 재귀함수는 처음에 볼 때는 이해하기 어려운 측면이 있는데,

누가 호출되고, 언제 그 계산이 되는지를 생각해보면 쉽게 이해할 수 있다.

 

이 두 가지 함수를 이해하기 위해서는

'팩토리얼'과 '피보나치'를 구현해보면 된다.

 

 

1-(1). 팩토리얼 반복문 사용

// 반복문 활용
public static int factorial(int number) {

    int sum = 1;
    for(int i = 2; i < number; i++) {
        sum *= i;
    }
    return sum;

팩토리얼은 n!으로 나타내며, 1부터 n까지의 모든 숫자를 곱한 값을 나타낸다.

반복문을 활용하면 쉽게 나타낼 수 있다.

 

sum이라는 변수를 두고, 초기값을 1로 설정한 다음, 반복문을 통해서 모든 숫자를 곱한 값을 sum에 저장한다.

그 다음 리턴을 하면 팩토리얼 값을 얻을 수 있는 함수를 만든 것이다.

 

 

1-(2). 재귀함수 사용

public static long factorial(long number) {
    if(number == 1) {
        return 1;
    }else {
        return number * factorial(number - 1);
    }
}

public static void main(String[] args) {
    System.out.println(factorial(50));
}
// 결과 : 2432902008176640000

재귀함수의 경우, 탈출할 수 있는 값을 구현하는 것이 필요하다.

예를 들어 매개변수가 1일 때, return 1을 한다던지 해서 탈출하게 하는 조건문이 필요하다.

그렇지 않으면, 무한하게 재귀 함수를 재귀 함수 내부에서 호출할 것이고, 재귀 함수는 종료되지 않고

결론적으로 값을 구할 수 없다.

 

재귀 호출의 방식은 아래 피보나치 재귀 함수에서 자세하게 살펴본다.

 

 

2-(1). 피보나치 반복문 사용

// 반복문 활용
public static int fibo(int number) {
    int one = 1;
    int two = 1;
    int result = -1;
    if (number == 1) {
        return one;
    }else if (number == 2) {
        return two;
    }else {
        for(int i = 2; i < number; i++) {
            result = one + two;
            one = two;
            two = result;
        }	
    }
    return result;
}

피보나치는 

1, 1, 2 ,3, 5, 7, 12, .....

이렇게 전전값과 전값을 더한 값이 현재값이 되는 수열을 말한다.

첫째 값과 둘째 값은 1, 1이 된다. 그렇기 때문에 초기 one, two 변수에 1을 저장해준다.

매개변수로 들어온 number 값이 1또는 2인 경우, 각각 one, two를 반환하고, 그것이 아닌 경우,

그 수까지 i = 2부터 반복문을 number 이전까지 돌려준다.

result 값을 -1로 초기화해두었는데, 이 result 변수에 one + two한 값을 저장하고,

one을 two로 바꾸고, two를 result로 바꾼다.

 

이렇게 하면 number가 숫자가 커져도 자동으로 변수들이 변경되면서

result값,즉 number번 째의 피보나치 수를 구할 수 있다.

 

 

2-(2). 피보나치 재귀함수 사용

public static int fibo(int number) {
    if(number == 1) {
        return 1;

    }else if(number == 2) {
        return 1;
    }else {
        return fibo(number - 1) + fibo(number - 2);
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(fibo(50));

}
// 50은 출력되지 않음

재귀함수를 더 자세하게 설명해본다.

 

피보나치의 경우, 팩토리얼과는 달리 매개변수를 50으로 주면 값이 출력되지 않는다.

왜냐하면, 함수 안에서 재귀함수를 두 번 호출하게 되는데, 결국 컴퓨터는 2의 50제곱번 연산을 해내야 하는 부담을 안게되기 때문이다.

2의 50제곱이면...

 

1,125,899,906,842,624

 

1125조 8999억 684만 2624번의 연산이 필요하다.

보통 자바가 1초간 5천만번의 연산을 한다고 가정하면,

32일 정도의 시간이 걸릴 것이다.

이런 프로그램은 뭐 프로그램이라고 부를 수가 없다. 32일을 어떻게 기다리나!

 

이런 것을 방지하기 위해서 다이내믹 프로그래밍이라는 것을 사람들이 발명을 해냈다.

이것은 나중에 다이내믹 프로그래밍을 포스팅 할 때 다시 알아보고...

 

이번에는 그냥 재귀함수가 누구를 호출하는지, 언제 연산이 되는 지를 알아보자.

 

 

 

 

1 ~ 14의 과정을 보면 된다.

(13)은 f(3)과 f(2)를 더해주는 과정이다.

(14)에서 최종 리턴값 5를 반환해주는 것을 볼 수 있다.

 

---

재귀함수는 자신 안에 들어있는 함수를 모두 호출해서 리턴값이 있을 때까지 침투해서 들어가고,

값을 얻은 때부터 하나씩 거슬러 올라와서 구하고자 하는 값을 반환해주는 것을 알 수 있다.

---