재귀

재귀 (Recurssion)

함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출

1. Base Part : 재귀를 끝나는 조건을 지닌 파트
2. Inductive Par : 자기 자신을 호출하는 파트

재귀의 호출은 프로그램 메모리 구조에서 스택을 사용하기 때문에, 반복적인 호출은 메모리 및 속도의 성능 저하를 야기한다.

예제

팩토리얼

int factorial(int n){
if (n==1 || 0) return 1;
else
return n*factorial(n-1);
}

Permutation

public class PermutationTest {

	static int N =3, R =4;
	static int[] numbers;
	static int[] input;
	static boolean[] isSelected;
	
	public static void main(String[] args) {
		input = new int[] {1,4,7,8};
		numbers = new int[R];
		isSelected = new boolean[N+1];
		permutation(0);
		
	}
	private static void permutation(int cnt) {
		//cnt == 목표
		if(cnt ==R ) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
	
		for(int i=1; i<=N;i++) {
			if(isSelected[i]) {continue;} //사용중인수면 다음수로
			numbers[cnt] =i;
			isSelected[i] =true;
			permutation(cnt+1);
			isSelected[i] = false;
		}
	}

}

Combination

public class Combination {
    public static void main(String[] ar){
        Combination ex = new Combination();
        int[] arr = { 1, 2, 3 };
        int n = arr.length;
        int r = 2;
        int[] combArr = new int[n];
 
        combination(combArr, n, r, 0, 0, arr);
    }
 
    public static void combination(int[] combArr, int n, int r, int index, int target, int[] arr){
        System.out.println("=> "+n+" "+r+" "+index+" "+target);
        if(r == 0){
            System.out.println(Arrays.toString(combArr));
            for(int i=0; i<index; i++)System.out.print(arr[combArr[i]] + " ");
           
            System.out.println();
         
        }else if(target == n){ 
            return;
         
        }else{
            combArr[index] = target;
            // (i) 뽑는 경우 :  r-1 , index +1
            combination(combArr, n, r-1, index+1, target+1, arr);
             
            // 안 뽑는경우 -> r과 index 그대로
		       combination(combArr, n, r, index, target+1, arr); 
        }
    }
}