재귀(Recursion) 알고리즘과 피보나치 수열

1. 재귀 알고리즘

재귀(Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출해서 문제를 해결하는 함수를 말한다. 재귀함수는 자신의 로직을 내부적으로 반복하여 문제를 해결하고 조건이 만족되면 함수를 이탈해서 결과를 도출한다. 따라서 재귀함수는 함수 내에서 자기 자신을 계속 호출하기 때문에 반드시 종료하는 부분을 정확히 구현해야한다. 그리고 함수를 호출할 때마다 메모리상에서 추가적으로 생긴다. 

public class Recursion_Test {
    public static void main(String[] args) {
        recursion();
    }

    //재귀함수
    public static void recursion(){
        System.out.println("안녕하세요");
        recursion();
    }
}

위의 코드를 보면 아무런 조건 없이 recursion()이라는 자기 자신만을 호출 하고있어 무한루프에 빠지게된다.

public class Recursion_Test {
    public static void main(String[] args) {
        recursion(5);
    }

    //재귀함수
    public static void recursion(int num) {
        if (num == 0) {
            return; //0일 경우 멈춤
        } else {
            System.out.println("안녕하세요");
            num -= 1;
	          System.out.println(num); //num이 3이면 3,2,1
            recursion(num);
		        System.out.println(num); //num이 3이면 1,2,3 - 함수가 호출되고 종료된 시점에 출력
        }
    }
}

따라서 이렇게 매개변수를 통해 메서드의 return하게 되는 구문을 구현하여 정확히 재귀 함수의 호출을 종료할수 있게 만들어야한다. 따라서 이렇듯 무한루프에 빠지지 않도록 주의하며 코드를 작성해야한다.

그리고 재귀호출의 앞뒤로 수행되는 시점이 달라 출력이 다르므로 주의해야한다.

예제1. 1+N까지의 합계출력

public class RecursionEx01 {
    static int sum= 0;
    public static void main(String[] args) {
        int n =10;
        recursive(n);
        System.out.println(sum);
    }
    public static void recursive(int n){
        if(n ==0){
            return;
        }else {
            sum += n;
            recursive(n-1);
      }
  }

예제2. 피보나치 수열

피보나치 수열이란 앞의 두 수의 합이 다음 수가 되는 수열을 말한다. 첫째 및 둘째 항은 1이다. 1,1,2,3,5,8,13,21,34

 

1) 재귀를 이용한 피보나치 수열 구하기

public class FibonacciEx01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            System.out.println(recursion(i)); //1,2,3,4,5
        }
    }
    public static int recursion(int n) {
        if (n <= 2) { //피보나치 수열은 처음과 두번째 숫자가 1
            return 1;
        } else {
            return recursion(n - 1) + recursion(n - 2);
        }
    }
}

2) 재귀를 이용한 피보나치 수열 구하기

public class FibonacciEx02 {
    static int[] arr; //피보나치 수열 넣을 배열
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        //n이 10이면 10개의 피보나치 수열 출력. 배열은 0부터 시작하니까 n+1
        arr =new int[n+1];

        //한번만 호출
        recursion(n);
        for(int i =1; i<=n; i++)
            System.out.print(arr[i] + " ");
    }
    public static int recursion(int n){
        if(n <=2) {
            return arr[n] = 1; //배열에 넣고 리턴
        }else {
            return arr[n] = recursion(n-1) + recursion(n-2);
        }
    }
}

위의 두 방법은 재귀를 이용해 피보나치 함수를 구하는 방법이다. 1번 방법보다 2번방법이 조금 더 효율적인데 1번방법은 n이 5라고 가정했을때 1부터 n까지의 숫자를 모두 재귀함수를 사용해 마지막에 나온 값을 출력하은 예제이고, 두번째는 n 을 한번만 호출하여 배열에 값을 넣고 재귀함수를 호출하는 방식이다. 하지만 이 두 방법모두 이미 계산되었던 값이라도 의미없이 다시 반복해서 방법하기 때문에 비효율적이다.

이때 한함수가 두개의 함수호출해 호출이 2배로 늘어나고, 계속 2배씩 늘어나므로 시간복잡도는 O(2^N)이라고 할수있다.

이때 재귀함수에서 이미 연산했던 값을 메모리에 저장하는 방식의 메모이제이션 방법을 통해 효율적으로 개선할 수 있다.

 

3) 재귀와 메모이제이션을 이용한 피보나치 수열 구하기

 

메모이제이션(Memoization)은 동적 프로그래밍 방법 중 하나로, 프로그램이 동일한 계산을 반복할때 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복수행을 제거해 프로그램 실행속도를 빠르게 한다.

public class FibonacciEx02 {
    static int[] arr; //피보나치 수열 넣을 배열
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        //n이 10이면 10개의 피보나치 수열 출력.
        //배열은 0부터 시작하니까 n+1
        arr =new int[n+1];
        //한번만 호출
        recursion(n);

        for(int i =1; i<=n; i++)
            System.out.print(arr[i] + " ");
    }
    public static int recursion(int n){
        if(n <=2) {
            return arr[n] = 1; //배열에 넣고 리턴
        }else {
            return arr[n] = recursion(n-1) + recursion(n-2);
        }
    }
}

이 방법은 메모이제이션을 통해 답을 저장하고 중복되는 계산을 반복수행을 없애므로 시간복잡도가 O(N) 이다.

예제3. 재귀를 이용해 배열에서 최대값 찾기

public class RecursionEx03Ver2 {
    public static int arr[] = {1, 2, 4, 8};

    public static void main(String[] args) {
        int n = arr.length;
        System.out.println(recursion(n));
    }

    public static int recursion(int n) {
        if (n == 1) { //배열의 원소가 하나일때 리턴
            return arr[0];
        } else {
            int x = Math.max(arr[n - 1], recursion(n - 1));
            //x와 n은 다름 ,x는 확인을 위해 출력
            //System.out.println(x);
            return x;
        }
    }
}

 

2. 재귀 알고리즘의 특징

1. 지속적으로 함수를 호출하면서 변수나 결과값이 모두 스택에 저장되어 메모리를 더 많이 사용하게 되어 속도 저하가 일어날 수 있다.
2. 종료문을 정확히 구현해 무한루프에 빠지지 않도록 주의하여야한다.
3. 이론적으로 반복문 ↔ 재귀 방법 구현이 가능하다.