재귀함수, 재귀적 사고

오늘은 재귀함수와 재귀적 사고에 대해 포스팅하겠다. 솔직히 '재귀'로 풀어야 하는 문제에는 여전히 약간? 쫄지만 반복만이 살길이다..ㅋㅋ

 

 

 

💡재귀 함수란 ?

재귀 함수란, 자기 자신을 호출하는 함수로 다음과 같이 간단하게 예를 들 수 있다.

public void DFS(int n){
    if(n==0) return;
    else{
        DFS(n - 1);
        System.out.print(n+" ");
    }
}

위 함수 DFS는 매개변수 n에서 부터 1까지를 출력하는 함수로, 자기 자신을 다시 호출하여 재귀적으로 문제를 해결하고 있다.

 

 

 

💡재귀 함수의 장점과 단점 

재귀 함수를 이용하면 불필요하게 여러 개의 반복문을 사용하지 않고 코드를 간결하게 작성할 수 있으며, 수정에도 용이하다. 또, 변수를 여러 개 사용할 필요가 없다는 장점이 있다.

하지만, 반복문과 달리 코드의 흐름을 직관적으로 파악하기 어렵고, 반복하여 메서드를 호출하기 때문에 지역변수, 매개변수, 반환값을 모두 process stack에 저장하여 반복문에 비해 더 많은 메모리를 사용하게 된다. 또, 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭  비용이 발생하게 된다는 단점이 있다.

 

 

그렇다면 재귀 함수는 언제 사용하는 것이 좋을까?

 

 

 

💡재귀 함수를 이용하기 위한 조건

먼저 문제의 크기를 작은 단위로 쪼갤 수 있는 경우, 재귀 함수를 사용하면 좋다. 또, 재귀 호출이 종료되는 시점, 즉 재귀 탈출 시점이 존재해야 한다.

 

 

 

그럼 다음 예제를 한번 보자.

 

 

 

📑팩토리얼을 반복문과 재귀함수를 사용하여 각각 구현해보자.

int n(n은 0이상 양수)을 매개변수로 입력받아 n!=nx(n-1)x(n-2)x.....x1 의 값을 리턴해야 한다.

 

우선 반복문으로 구현한 코드를 보자.

public int factorial1(int n){
    int result=1;
    for(int i=1;i<=n;i++){
        result=result*i;
    }
    return result;
}

반복문으로 구현하면 i를 1~n까지 증가시켜가면서 n!의 결과값을 리턴할 수 있다.

 

 

그렇다면 재귀적으로 어떻게 문제를 해결할까?

예를 들어 n=5라 가정하면 5!=5*4*3*2*1 이다. 하지만 5!은 5!=5*4!으로도 표현이 가능하다.

5!=5*4!

4!=4*3!

3!=3*2!

2!=2*1!

1!=1*0!

즉, n!=n*(n-1)!으로 나타낼 수 있다.

 

따라서 이를 이용하여 재귀적으로 코드를 작성하면 다음과 같이 작성가능하다.

public int factorial2(int n){
    if(n<=1) return 1;
    else {
        return n*factorial2(n-1);
    }
}

이렇게 재귀함수를 이용하면 좀 더 코드를 간결하게 작성이 가능하다.

 

 

 

일반적인 재귀 함수의 템플릿은 다음과 같다.

public type recursive(input1, input2, ... ){
    //Base Case : 문제를 더 이상 쪼갤 수 없는 경우, 탈출 시점
    if(문제를 더 이상 쪼갤 수 없는 경우){
        return 단순한 문제의 해답;
    }
    //recursive Case : 더 작은 문제로 쪼갤 수 잇는 경우
    return 더 작은 문제로 새롭게 정의된 문제;   
}

 

 

추가로 피보나치 수열 예제를 살펴보자.

 

📑피보나치 수열을 반복문과 재귀함수, 메모이제이션를 사용하여 각각 구현해보자.

int n을 매개변수로 받고 n개의 피보나치 수열 리턴.

피보나치 수열은 1, 1, 2, 3, 5, 8, 13 .. 처럼 어떤 수 n이 앞의 두수 n-1,n-2의 합으로 표현되는 경우를 말한다.

 

우선 반복문으로 피보나치 수열을 나타내보자.

public int[] fibo1(int n){
    int[] arr = new int[n];
    arr[0]=1;
    arr[1]=1;
    for (int i = 2; i < n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr;
}

 

다음은 재귀함수로 피보나치 수열을 나타내보자.

public int fibo2(int n){
    if(n==1 || n==2) return result[n]=1;
    return result[n]=fibo2(n-1)+fibo2(n-2);
}

 

마지막으로 메모이제이션으로, 반복해서 접근하는 연산을 줄이도록 코드를 작성해 보자.

public int fibo3(int n){
    if(dp[n]>0) return dp[n];
    if(n==1 || n==2) return dp[n]=1;
    else return dp[n] = fibo3(n - 1) + fibo3(n - 2);
}

dp배열로 이미 연산한 fibo는 다시 방문하지 않도록 한다.

 

 

 

전체 코드는 다음과 같다.

package codingTest.inflearn;

import java.util.ArrayList;
import java.util.Arrays;

public class Sol44_2 {

    static int[] dp;
    static int[] result;

    //반복문
    public int[] fibo1(int n){
        int[] arr = new int[n];
        arr[0]=1;
        arr[1]=1;
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }

    //재귀
    public int fibo2(int n){
        if(n==1 || n==2) return result[n]=1;
        return result[n]=fibo2(n-1)+fibo2(n-2);
    }

    //메모이제이션
    public int fibo3(int n){
        if(dp[n]>0) return dp[n];
        if(n==1 || n==2) return dp[n]=1;
        else return dp[n] = fibo3(n - 1) + fibo3(n - 2);
    }


    public static void main(String[] args) {
        Sol44_2 s = new Sol44_2();
        System.out.println("반복문으로 만든 fibo");
        System.out.println(Arrays.toString(s.fibo1(8)));


        result = new int[9];
        System.out.println("재귀함수로 만든 fibo");
        s.fibo2(8);
        for(int i=1;i<result.length;i++) System.out.print(result[i]+", ");

        System.out.println();

        dp = new int[9];
        System.out.println("메모이제이션을 활용한 fibo");
        s.fibo3(8);
        for(int i=1;i<result.length;i++) System.out.print(result[i]+", ");

    }
}

 

 

이렇듯 재귀는 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우, 또는 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우에 사용하면 적합하다.