재귀 알고리즘(팩토리얼, 최대공약수, 피보나치 수열, 하노이의 탑, 8퀸문제 예제)

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의 될 때 재귀적 이라고 한다.

재귀함수란?

자기 자신을 호출하는 함수!

처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다

 

즉! 종료조건이 충족될때까지

https://www.youtube.com/watch?v=aPYE0anPZqI

작업을 수행하는 것!

재귀함수는 for문이나 while문으로 대체 가능하다!

그런데 재귀함수를 사용하는 이유 → 코드가 간결해지고, 유지보수가 쉬어

재귀함수는 호출될때마다 메모리의 스택이 쌓인다.

한계치 이상으로 호출돼서 스택이 넘치면 메모리 부 에러.

속도면에서도 재귀함수는 jump가 잦아서 반복문에 비해 시간을 더 소요한다.

이 문제를 해결하기위해 꼬리 재귀 최적화를 지

선형알고리즘으로 만들어 실행! 그러면 스택이 넘치지 않음!

📌 팩토리얼 구하기

package chap05_Recrusion;

import java.util.Scanner;

public class Factorial {

	static int factorial(int n) {
		if (n > 0)
			return n * factorial(n - 1);
		else
			return 1;
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();

		System.out.println(N + "! = " + factorial(N));

	}

}

//5
//5! = 120

5 * 4 * 3 * 2 * factorial ( 1 )

📌 최대공약수, 최소공배수

package chap05_Recrusion;

import java.util.Scanner;

public class GCD_LCM {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		sc.close();

		System.out.println(x + "와 " + y + "의 최대공약수는? :" + GCD(x, y));
		System.out.println(x + "와 " + y + "의 최소공배수는? :" + LCM(x, y));
	}

	static int GCD(int x, int y) {
		if (y == 0)
			return x;

		return GCD(y, x % y);
	}

	// 최소공배수 구하기
	public static int LCM(int x, int y) {
		// 최소공배수는 두 수를 곱하고 최대 공약수로 나눈다.
		// 예) 6 10 -> 6 * 10 / 2 .... 즉 30이 최소공배수
		return x * y / GCD(x, y);
	}

}

//6 10
//6와 10의 최대공약수는? :2
//6와 10의 최소공배수는? :30

📌 피보나치 수열

어떤 수열의 합이 앞의 두항의 합과 같은 수열

1 1 2 3 5 8 13 21 34 55

package chap05_Recrusion;

import java.util.Scanner;

public class Fibonacci {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int totalN = sc.nextInt();
		int findNum = sc.nextInt();
		sc.close();

		for (int i = 0; i < totalN; i++) {
			System.out.print(fibo(i) + " ");
		}
		System.out.println("\\n" + findNum + "번째 숫자는? : " + fibo(findNum));
	}

	static int fibo(int n) {
		if (n <= 1) {
			return 1;
		} else {
			// 피보나치 수열은 앞의 두항의 합이 협재의 항의 값이 된다
			return fibo(n - 1) + fibo(n - 2);

		}
	}
}

//13
//5
//console
//1 1 2 3 5 8 13 21 34 55 89 144 233 
//5번째 숫자는? : 8

📌 하노이의 탑

시작 기둥, 중간기둥 ,목표기둥

맨왼쪽 시작기둥의 원반을 목표기둥으로 옮기자

하노이탑 : 큰수부터 차례대로 있어야함.

방법 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B11729 {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		// 총 경우의 수 = 2^n - -1
		sb.append((int)Math.pow(2, N) - 1 + "\\n");

		move(N, 1, 3);

		System.out.println(sb);
	}

	/*
	 * num : 원판의 개수 from : 출발지 to : 목적지
	 */

	static void move(int num, int from, int to) {

		if (num > 1)
			move(num - 1, from, 6 - from - to);

		sb.append(from + " " + to + "\\n");

		if (num > 1)
			move(num - 1, 6 - from - to, to);
	}
}

방법2.

void hanoi(원판의 수, 시작, 목표, 보조) {
    if (원판의 수 == 1) {
        System.out.println(시작 + "->" + 목표);
        return;
    }
    hanoi(원판의 수 - 1, 시작, 보조, 목표);
    System.out.println(시작 + "->" + 목표);
    hanoi(원판의 수 -1, 보조, 목표, 시작);
}

https://devlimk1.tistory.com/153

[재귀] java 코드로 하노이 탑 쉽게 이해해보자! by.펜잡이 개발자