재귀 알고리즘

📝 문제 풀이

1. 종료조건(필수)
2. 처리

💡 내 코드

팩토리얼

package 팩토리얼;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("숫자를 입력");
		int n = sc.nextInt();
		int result = factorial(n);
		System.out.println(result);
	}
	
	static int factorial(int n) {
		if(n ==0)   
			return 1; //종료조건 작성
		return n*factorial(n-1);
	}
}

💡 내 코드

중복되는 경우의 수 (완전탐색 ,dfs)
중복이 안되면 -> 순열

package 팩토리얼;

public class 경우의수 {
	
	// static 에서 static으로 접근하기 위해
	static int[] arr = {1,2,3};  	 
	static int[] result = new int[3]; 
	static int n = 3;
	
	public static void main(String[] args) {
		//주어진 원소를 이용한 생성가능한 모든 경우의 수(
		// {1,2,3} ->123,132,213,231,312,321 (중복불가능
		// {1,2,3} ->111,112,113 (중복허용)
		
		arr = new int[]{1,2,3}; 	//1. 원소 저장,선언이후에 값을 저장하려면 new int[]을 써줘야함
		result = new int[arr.length]; //2. 답 저장
		n = 3;// 추출의 개수			//3 . 반복 횟수
								//4. 재귀호출 =>패턴화
								//1) 깊이가 3이면 종료
	
		recur(0);
		
	}

	private static void recur(int depth) {
		if(depth ==n) {	//n은 main메소드 안에 있기때문에 밖으로 빼서 전역변수로 만들어줘야함
			print();	//종료조건
			return;
		}
		//깊이의 숫자위치에 i값을 저장
		for (int i = 0; i < arr.length; i++) {
			result[depth]=arr[i];
			recur(depth+1);
		}
		
		
	}

	private static void print() {
		for (int i :result) {
			System.out.print(i);
			
		}
		System.out.println();
		
	}

}

💡 내 코드

순열

public class 순열 { // 숫자는 1번씩 사용됨

	// static 에서 static으로 접근하기 위해
	static int[] arr = {1,2,3};  	 
	static int[] result = new int[3]; 
	static int n = 3;
	static boolean[] visited; //사용여부 저장
	
	public static void main(String[] args) {
		//주어진 원소를 이용한 생성가능한 모든 경우의 수(
		// {1,2,3} ->123,132,213,231,312,321 (중복불가능
		// {1,2,3} ->111,112,113 (중복허용)
		
		arr = new int[]{1,2,3}; 	//1. 원소 저장,선언이후에 값을 저장하려면 new int[]을 써줘야함
		result = new int[arr.length]; //2. 답 저장
		n = 3;// 추출의 개수			//3 . 반복 횟수
								//4. 재귀호출 =>패턴화
								//1) 깊이가 3이면 종료
		visited = new boolean[arr.length]; //
		recur(0);	
	}
	private static void recur(int depth) {
		
		if(depth ==n) {	//n은 main메소드 안에 있기때문에 밖으로 빼서 전역변수로 만들어줘야함
			print();	//종료조건
			return;
		}
		//깊이의 숫자위치에 i값을 저장
		for (int i = 0; i < arr.length; i++) {
			if(visited[i]==false) {//i번째 숫자가 미사용
				result[depth]=arr[i];
				visited[i] =true;
		    	recur(depth+1);
		    	
		    	visited[i] = false; // true->false로 초기화 시켜주기 위해
			}
		}
	}

	private static void print() {
		for (int i :result) {
			System.out.print(i);		
		}
		System.out.println();	
	}
}