알고리즘1-5. 재귀알고리즘

재귀 함수(Recursive Functions)

• 하나의 함수에서 자신을 다시 호출하는 함수
• 일반적으로 재귀적 정의를 이용해 재귀함수를 구현한다. (기본부분:basic part와 유도 파트(inductive part)로 구성
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다. 재귀 호출은 반복적인 스택의 사용을 의미하고 계속 재귀함수를 호출하면 메모리 및 속도에서 성능저하가 발생한다. 
• 재귀 함수를 문제 풀이에서 사용할 때는 재귀함수의 종료 조건을 반드시 명시해야 한다.(종료 조건을 명시하지 않으면 함수가 무한히 호출될 수 있다.)

 

 

---

예제) 팩토리얼 구하기

 

1. for문을 이용한 팩토리얼 구하기

 

import java.util.Scanner;

public class Factorial {

	// for문을 이용한 팩토리얼 구하기
	static int factorial1(int max) {
		// 5*4*3*2*1
		int result = 1; // 계산한 결과를 저장할 변수를 생성 1로 초기화를 해줘야 들어오는 값이 변하지 않음
		
		for(int i=max; i>1; i--) { // 5,4,3,2,1
			result *= i;
		}
		return result;
	}

	public static void main(String[] args) {
    
		Scanner s = new Scanner(System.in);
		System.out.print("팩토리얼로 구할 수 입력: ");
		
		// 입력한 수까지 팩토리얼 구하기
		int max = s.nextInt();
		
		// for문을 이용한 팩토리얼 구하기
		int result1 = factorial1(max);
		System.out.println("f1 -> " + result1);
        
		s.close();
	}
}

 

예) int max = 4일때,  int i == max

 

result = result(1) * i(4) -> result = 4 

result = result(4) * i(3) -> result = 12

result = result(12) * i(2) -> result = 24

 

for문에서 i가 2까지이기 때문에 for문 실행중지 (만약 i>=1이어도 어차피 result(24) * i(1)이기 때문에 굳이 1을 안곱해줘도 된다.)

 

2. 재귀호출로 팩토리얼 구하기

 

import java.util.Scanner;

public class Factorial {

	// 재귀호출로 팩토리얼 구하기
	static int result = 1;  // 재귀함수에서 사용하기 위해서(메서드가 static이므로 static으로 전역변수로 선언)
	
	public static void factorial2(int max) {  // 5,4,3,2,1
		
		if(max<=1) return; // return을 만나면 멈춤 / 재귀호출 중단
		result *= max;
		factorial2(max-1);  // 4,3,2,1,0 계속해서 1씩 감소 , 중단하지 않으면 무한으로 계속 실행
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.print("팩토리얼로 구할 수 입력: ");
		
		// 입력한 수까지 팩토리얼 구하기
		int max = s.nextInt();
		
		// 재귀호출로 팩토리얼 구하기
		result = 1;  // factorial2를 또 호출할 수도 있기 때문에 result를 초기화 해줘야 한다.
		factorial2(max);
		System.out.println("f2 -> " + result);
		
		s.close();
	}
}

 

예) int max = 4일때, factorial2(4)이다. 

 

max(4)<=1 이어서(거짓이어서 식 실행, 참이면 return)

result = result(1) * max(4) -> result = 4

factorial2(3) 호출!

 

factorial2(3) 이면, int max = 3;

max(3)<=1 이어서(거짓이어서 식 실행)

result = result(4) * max(3) -> result = 12 

factorial2(2) 호출!

 

factorial2(2) 이면, int max = 2;

max(2)<=1 이어서(거짓이어서 식 실행)

result = result(12) * max(2) -> result 24

factorial2(1) 호출!

 

factorial2(1) 이면, max(1)<=1 -> 참이기 때문에 현재 저장된 result 값 반환!

 

3. 반환 값이 있는 재귀호출로 팩토리얼 구하기(팩토리얼 구현 결과를 구현하는 방법)

 

import java.util.Scanner;

public class Factorial {
	
	// 반환값이 있는 재귀호출로 팩토리얼 구하기
	public static int factorial3(int max) {
		if(max<=1) return 1; // 곱하는 데이터에 영향을 주지 않기 위해서 1을 return
		return max* factorial3(max-1); // max가 1이면 실행 xx 그 전에 있던 재귀함수로 
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.print("팩토리얼로 구할 수 입력: ");
		
		// 입력한 수까지 팩토리얼 구하기
		int max = s.nextInt();
		
		int r = factorial3(max);
		System.out.println("f3 -> " + r);

		s.close();
	}
}

 

예) int max = 4일때, 

 

return max(4) * factorial3(max(4)-1) 

return max(4) * factorial3(3) * factorial3(max(3)-1) => max(4) * 3 * factorial3(2) 

return max(4) * factorial3(3) * factorial(max(2)-1) => 4 * 3 * 2

 

if(max<=1)이 true가 되면서 return 1, return 4*3*2 = 24

 

4. while문을 이용한 팩토리얼 구하기

 

import java.util.Scanner;

public class Factorial {
	
	// 팩토리얼 구하기(while문)
	public static int factorial4(int max) {
		int result = 1;	
		
		while(true) {
			if(max<=1) return result;
			result *= max;
			max--;
		}
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.print("팩토리얼로 구할 수 입력: ");
		
		// 입력한 수까지 팩토리얼 구하기
		int max = s.nextInt();

		System.out.println("f4 -> " + factorial4(max));
		
		s.close();
	}
}

 

예) int max = 4일때,  

 

result = result(1) * i(4) -> result = 4,  max 4-1 = 3

result = result(4) * i(3) -> result = 12, max 3-1 = 2

result = result(12) * i(2) -> result = 24, max 2-1 = 1

 

if(max<=1)가 조건이 되면서 현재 result값이 return!