[알고리즘]재귀함수(Recursion)

재귀함수(Recursion)

• 메소드 정의시 자기 자신을 재참조하는 방법(=재귀호출)
• 무한 루프에 빠질 수 있는 위험이 있다.
• 스택 메모리를 차지하기 때문에 반복적 호출로 인해 스택 메모리가 커지게 되면 StackOverflow가 발생한다.
• 알고리즘 표현시 반복문보다 구현이 용이할 수 있다.

아래는 재귀함수의 단적인 예이다.

package com.company;

public class Recursion {

	public static void main(String[] args) {
		Danger();
	}
	
	public static void Danger() {
				
		System.out.println("실행");
		
		Danger();
	}
}

이 경우 무한 루프에 빠져 StackOverflowError를 내뱉는다. 때문에 재귀함수를 사용하는 경우에는 예외처리를 반드시 해주어야 한다.

package com.company;

public class Recursion {

	public static void main(String[] args) {
		Danger(5);
	}
	
	public static void Danger(int cnt) {
		if(cnt == 0) {
			return;
		} 		
		
		System.out.println("실행");				
		
		cnt = cnt - 1;
		
		Danger(cnt);
	}
}

 

재귀함수를 이용한 알고리즘

1. 피보나치 수열

피보나치 수열은 다음과 같은 규칙을 만족하는 수열을 말한다.

• 첫 항과 두번째 항은 1로 시작, 세번째 항은 첫 항+두번째 항이 된다.
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...)

package com.algorithm;

public class Fibonacci {

	public static void main(String[] args) {
		
		int result = 10;
		  
		for(int i = 1; i <= result; i++) { 
			System.out.println(Fibo(i));
		}
		 	
	}
	
	/**
	 * 피보나치 수열
	 * 첫 항과 두번째 항은 1로 시작하며 세번째 항은 첫 항과 두번째 항의 합이 된다.
	 * 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...)
	 * @param n
	 * @return
	 */
	public static int Fibo(int n) {
		if(n <= 1) {			
			return n;
		} else {			
			return Fibo(n-2)+Fibo(n-1);
		}		
	}
}

 

2. 유클리드 호제법 : 최대공약수 구하기

유클리드 호제법은 주어진 두 수 사이에 최대공약수(GCD)를 구하는 알고리즘이다.

• m > n일 때, m을 n으로 나눈값이 0이라면 n은 최대공약수이다.
• 만약 m을 n으로 나눈 값이 0이 아니라면 m에 n값을 넣고, m%n값을 n에 대입 후 다시 반복한다.

package com.algorithm;

public class Euclidean {

	public static void main(String[] args) { 
		System.out.println(Euclidean(128, 96));
	}

	/**
	 * 유클리드 호제법
	 * 주어진 두 수 사이에 최대공약수(GCD)를 구하는 알고리즘
	 * m > n일 때, m을 n으로 나눈 값이 0이라면 n은 최대공약수이다.
	 * @param m
	 * @param n
	 * @return
	 */
	public static int Euclidean(int m, int n) {
		if(m < n) {
			int temp = 0;
			
			temp = m;
			m = n;
			n = temp;
		}
		
		if(m % n == 0) {
			return n;
		} else {
			return Euclidean(n, m%n);
		}
	}
}

 

3. 하노이탑

재귀함수의 대표적 예제로서 3개의 기둥에서 가운데 기둥을 이용해 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽으로 옮기는 문제이다. 다음과 같은 규칙이 있다.

• 원판은 한 번에 하나씩 옮길 수 있다.
• 크기가 작은 원판 위에는 크기가 큰 원판이 놓일 수 없다.
• 원판을 모두 옮기는데 걸리는 시간은 [2의 n승 - 1] 이다.

그림으로 보면 이해가 쉽다.

package com.algorithm;

public class Hanoitop {

	public static void main(String[] args) {		
		int floor = 3;
		
		hanoitop(floor, "A", "B", "C");
	}
	
	/**
	 * 하노이탑
	 * 재귀함수의 대표적 예제로 3개의 기둥에서 가운데 기둥을 이용해 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽으로 옮기는 문제.
	 * @param n
	 * @param left
	 * @param center
	 * @param right
	 */
	public static void hanoitop(int n, String left, String center, String right) {
		if(n == 1) {
			System.out.println("원판 1을 " + left + "에서 " + right + "로 옮김");
		} else {
			hanoitop(n - 1, left, right, center);
			System.out.println("원판 " + n + "을 " + left + "에서 " + right + "로 옮김");
			hanoitop(n - 1, center, left, right);
		}
	}
}

---

+ 피드백은 언제나 환영입니다 :)