재귀함수를 이용한 자바 프로그래밍

재귀함수란 자기 함수, 메소드안에 자신 메소드가 들어있는 것을 말한다.

 

* factorial이란 n!처럼 주어지면 n이 1에 도달 할때까지 수를 하나씩 감소하며 계속 곱하는 것을 말한다.

다시말해 다음과 같이 5! = 5 x 4 x 3 x 2 x 1 이다.

n의 수가 커질수록 기하 급수적으로 결과가 커진다.

 

 
public class Main {
    
    public static int factorial(int number) {
        int sum = 1;
        for(int i = 1; i <= number; i++) {
            sum *= i;
        }
        return sum;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("10 팩토리얼의 값은 : " + factorial(10));
    }
 
}
 

주어진 n의 값에따라 팩토리얼을 다음과 같이 반복함수로 구현할 수 있다.

 

그런데 이것을 재귀 함수로 구현하면 어떻게 될까?

 

 
public class Main {
    
    public static int factorial(int number) {
        if (number == 1) {
            return 1;
        } else {
            return number * factorial(number -1);
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("10 팩토리얼의 값은 : " + factorial(10));
    }
 
}
 

factorial이라는 메소드안에 factorial메소드를 다시 넣은 형태이다.

1이 주어졌을 때는 1이 return되게 하고 number의 값을 하나씩 줄여

1까지 곱하게 만든 형태이다.

 

 

 

 

* 피보나치 수열은 n번째 수열의 값이 n-1, n-2번째 수열의 값의 합인 수열이다.

 

package baekjoon.first.io;
 
public class Main {
    
    public static int fibonacci(int number) {
        int one = 0;
        int two = 1;
        int sum = 0;
        if (number == 0) {
            return one;
        } else if(number == 1){
            return two;
        } else {
            for(int i = 0; i < number; i++) {
                sum = one + two;
                one = two;
                two = sum;
            }
            return sum;
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("10번째 피보나치 수열의 값은 : " + fibonacci(2));
    }
 
}
 

피보나치 수열또한 다음과 같이 반복함수를 통해 구현할 수 있다.

 

package baekjoon.first.io;
 
public class Main {
    
    public static int fibonacci(int number) {
        if(number == 0) {
            return 0;
        } else if(number == 1){
            return 1;
        } else {
            return fibonacci(number-2) + fibonacci(number-1);
        }
        
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("10번째 피보나치 수열의 값은 : " + fibonacci(10));
    }
 
}
 

이렇게 재귀함수 형태로 구현하면 훨씬 간결하게 코드를 작성할 수 있다.

 

* 그런데 이렇게 재귀함수로 구현하는 방식이 반드시 좋은것은 아니다.

 

만약 50번째 수열의 값을 구한다고 상상하면 그림처럼 쓸데없이 계속 반복되는 부분이 많다.

f(48)과 f(49)를 구하는 과정에서 이미 구했던 값을 다시 해야하는 것이다.

이처럼 만약 큰 수열의 값을 얻고자 한다면 연산과정은 기하급수적으로 늘어나 연산시간이 오래 걸릴 것이다.