재귀함수

우선 함수에 대해 알아보자

함수란 값을 입력받아 특정 연산을 수행하여 결과를 반환하는 것이다.

 

다음은 재귀 함수에 대해 알아보자

자기 자신을 부르는 함수

 

대표적인 예시는 팩토리얼이다.

import java.util.Scanner;

public class Main2 {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        System.out.println(getFactorial(n));

    }
    public static int getFactorial(int n){
        if (n==0)return 1;
        else return n*factory(n-1);
    }
}

 

위 코드를 보면 계속해서 자기 자신을 부른다.

즉 아래 그림과 같이 계속해서 getFactorial이 불러진다.

n의 값이 0이 될 때까지 자기 자신을 부른다.

이후 다시 올라가면서 돌아간다.

재귀는 아래 부르는 재귀 호출이 잘 작동된다고 가정하고 코드를 작성한다.

즉 getFactorial(4)는 3,2,1,0이 잘 작동한다고 가정한다.

 

우리는 getFactorial이 n팩토리얼을 잘 반환하는지 궁금하다.

따라서 아래와 같은 증명을 할 수 있다. 

수학적 귀납법

명제 P(n)이 모든 자연수 n에 대하여 성립함을 보이자.

*증명 순서

P(1)이 참임을 보인다.

P(k)가 성립한다고 가정한 후, P(k+1)이 성립함을 보인다.

따라서 모든 자연수 n에 대하여 P(n)이 성립한다.

 

1일 때 되면, 2일 때 된다. 2일 때 되면 3일 때 된다...... n이 된다.

즉 k가 된다면, k+1도 가능하다.

 

****재귀 함수 디자인****

1. 함수의 역할을 말로 정확하게 정의한다.

2. 기저 조건에서 함수가 제대로 동작함을 보인다.

3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다. 

 

 

 

재귀 함수를 이용한 Brute-Force

모든 경우를 시도해보는 코드를 짜기가 까다로운 경우

n 중 for문을 돌려야 한다??

 

ex) n개의 카드가 있고, 각각은 1부터 n까지의 번호를 갖는다. 이를 한 줄로 세울 수 있는 모든 경우를 출력하시오.

if) n =3

for(int i =1;i<=3;i++){
 for(int j=1;j<=3;j++){
  for(int k=1;k<=3;k++){
   if(i!=j&&j!=k&&i!=k){
   	System.out.println("%d %d %d",i,j,k);
    }
   }
  }
 }

위 코드를 보면, n의 값만큼 for문이 증가한다. + n의 값이 변한다면 반복문을 처리하기 어렵다.

 

 

재귀 함수를 이용하면 아래와 같다.

void getResult(int current,int n, int result[]){
        if (current>=n){
            System.out.println(result);
        }
        for (int i=1;i<=n;i++){
            if (isNotContaining(result,i)){
                result[current] = i;
                getResult(current+1,n,result);
                result[current]=0;
            }
        }
    }

currnet는 현재 배열의 index를 의미한다. n의 n까지의 번호 즉 n 중 for문이다.

result배열은 값을 넣어줄 배열이다.

isNotContaining은 중복 체크하는 함수이다. 

 

맨 처음 값은 아래 그림과 같이 된다.

위 배열 current 가 0일 때 즉 배열의 index가 0일 때 1을 넣고, 그다음 index로 넘어간다.

그리고 index1에서는 앞에 1이 있으므로 2가 들어가고, 다음 index로 들어간다.

이것을 보면 index 0, 1, 2가 3중 for문을 돌리는 것과 같다.

즉 index 0의 값이 1이고, 그다음 index1의 값은 1일 때, index2의 값은 1,2,3이 들어온다.

이후 index1의 값이 2가 된 후, 다시 index 2의 값이 1,2,3 반복된다.

 

 

재귀 함수 예제

N개의 알파벳 중에서 R개를 나열할 수 있는 경우를 모두 출력하시오.

 

정답 코드

import java.util.Scanner;

public class Main{
    static int n; //경우의 수
    static int r; //for문의 수
    static char[] arr;
    static boolean[] check;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        arr = new char[r];
        check = new boolean[n];
        alpa(0);
    }
    static void alpa(int x){
        if (x>=r){
            String str ="";
            for (int arr: arr){
                str+=(char)arr;
            }
            System.out.println(str);
            return;
        }
        for (int i=0;i<n;i++){
            char ch = (char)(i+'a');
            if (check[i]==false){
                check[i] = true;
                arr[x] = ch;
                alpa(x+1);
                check[i] = false;
            }
        }

    }
}

위 코드에서 중요하게 볼 것은 check배열인데, 이는 중복을 체크해주는 역할을 한다.

기저 조건의 경우 우리가 원하는 배열의 크기 이상이 되면 return 해준다.

 

 

 

다음 문제이다.

 

정답 코드

import java.util.Scanner;

public class Main {
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  //자리수
        int k = sc.nextInt();  //1의수
        arr = new int[n];
        funtion(k,0);
    }
    static void funtion(int k,int index){
        if (k==0){
            for (int arr:arr){
                System.out.print(arr);
            }
            System.out.println();
            return;
        }
        for (int i=index;i<arr.length;i++) {
            arr[i] = 1;
            funtion(k - 1, i + 1);
            arr[i] = 0;
        }
    }
}

이 코드는 기저 조건이 그 전과는 다르다.

1의 개수가 정해져 있으므로, 1을 모두 소모하게 되는 것이 기저 조건이다.

1을 초반에 다 소모하여도 뒤에 값은 0이 나오게 되는데, 이는 배열 초기값이 0으로 설정되기 때문이다.