제4장 재귀 호출

1. 제4장 재귀 호출
   1. 4.1. 자기 자신을 호출한다.
   2. 문서에 대하여

4.1. 자기 자신을 호출한다.

• 재귀적으로 문제를 해결함은 또 문제를 점점 더 작은 단위로 쪼개어서 해결함을 의미.

4.1.1. 잘못된 재귀 호출

• 무한루프로 된 재귀 호출
  • 장미는 장미다.

public static void rose() {
		rose();
	}

• • 철수는 영희 옆집에 산다. 영희는 철수 옆집에 산다.

public static void cheol() {
		young();
	}
	public static void young() {
		cheol();
	}

• • 알에서 새가 태어난다. 새가 알을 낳는다.

public static void egg() {
		bird();
	}
	public static void bird() {
		egg();
	}

• • 먹는다. 싼다. 잔다. 먹는다. 싼다. 잔다.

public static void eat() {
		output();
	}
	public static void output() {
		sleep();
	}
	public static void sleep() {
		eat();
	}

4.1.2. 재귀 호출의 요건

4.1.3. 누승을 구하는 재귀 함수.

• N의 누승은 N\! 라 표현한다.
  
  Info N\! = N * (N-1) * (N-2) * ... * 2 * 1
  = N * (N-1)\!, 단 0\! = 1
  

public static int factorial(int n) {
		//if(n == 0)
		if(n < 1) // 방어적 프로그래밍
			return 1;
		else
			return n * factorial(n - 1);
	}

• 결과(n=5)

120

• Trace해보자.

package com.oracleclub.study;

public class Factorial {

	private static int tab = 0;

	private static void printTab(String message) {

		for(int i=0; i<tab; i++) {
			System.out.print("\t");
		}
		System.out.println(message);

		tab++;
	}

	public static int factorial(int n) {
		//if(n == 0)
		if(n < 1) // 방어적 프로그래밍
			return 1;
		else
			return n * factorial(n - 1);
	}

	public static int traceFactorial(int n) {

		String debug = "factorial(" + n + ") -----> ";

		if(n < 1) {
			printTab(debug + "return 1\r\n");
			return 1;
		}
		else {
			printTab(debug + "return " + n + " * " + "factorial(" + (n-1) + ")");
			return n * traceFactorial(n - 1);
		}

	}

	public static void main(String[] args) {
		System.out.println(traceFactorial(5));
	}
}

• 결과(n=5)

factorial(5) -----> return 5 * factorial(4)
	factorial(4) -----> return 4 * factorial(3)
		factorial(3) -----> return 3 * factorial(2)
			factorial(2) -----> return 2 * factorial(1)
				factorial(1) -----> return 1 * factorial(0)
					factorial(0) -----> return 1

120

4.1.4. 피보나치의 수열을 구하는 재귀 함수

• 공식
  
  Info F[WEBSTUDY:N] = F[WEBSTUDY:N-1] + F[WEBSTUDY:N-2], 단 F[WEBSTUDY:1] = F[WEBSTUDY:2] = 1
  

package com.oracleclub.study;

public class Fibonacci {
	public static int fibonacci(int n) {
		if(n == 1 || n == 2)
			return 1;
		else
			return fibonacci(n-1) + fibonacci(n-2);
	}

	public static void main(String[] args) {
		System.out.println(fibonacci(5));
	}
}

• 결과

5

• 재귀 호출이 두 번 이상 있을 때 재귀 호출을 분석하는 가장 정확하고 명확한 방법은?? 재귀 나무를 작성하라.

4.1.5. 재귀 호출의 전략

• 1. 문제의 크기를 조금씩 줄여가는 방법.
• 2. 문제의 크기를 양분하는 방법.
• 3. 문제의 크기를 자르는 것이 아니라 자체에 접근해 가는 방법.

4.1.6. 하노이의 탑.

• 참고 : 하노이의 탑이란? 브라마 사원의 승려들에 의해 행해졌던 것.

package com.oracleclub.study;

public class Hanoi {

	public static void move(int from, int to) {
		System.out.println(from + "에서" + to + "로 움직였습니다.");
	}

	public static void hanoi(int n, int from, int by, int to) {
		if(n==1)
			move(from ,to);
		else {
			hanoi(n-1, from, to, by);
			move(from, to);
			hanoi(n-1, by, from, to);
		}

	}

	public static void main(String[] args) {
		int height=4;
		System.out.println("하노이 탑의 크기 : " + height);
		hanoi(height, 1, 2, 3);
		System.out.println("완료");
	}
}

• 결과

하노이 탑의 크기 : 4
1에서2로 움직였습니다.
1에서3로 움직였습니다.
2에서3로 움직였습니다.
1에서2로 움직였습니다.
3에서1로 움직였습니다.
3에서2로 움직였습니다.
1에서2로 움직였습니다.
1에서3로 움직였습니다.
2에서3로 움직였습니다.
2에서1로 움직였습니다.
3에서1로 움직였습니다.
2에서3로 움직였습니다.
1에서2로 움직였습니다.
1에서3로 움직였습니다.
2에서3로 움직였습니다.
완료

• 재귀 나무를 작성하라.

문서에 대하여

• 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
• 최초작성자 : 장선웅
• 최초작성일 : 2009년 2월 23일
• 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
• 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^