알고리즘 - 재귀 호출

✔재귀 호출

• 반복과 재귀는 유사한 작업 수행 가능

  • 반복은 수행하는 작업이 완료될 때까지 반복(for, while)
  • 재귀은 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법(분할 정복)
    • 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 작은 문제로 쪼개고 결과 결합.
    • 재귀 함수로 구현.

• 재귀 함수(Recursive Function)

  • 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수
  • 일반적으로 재귀적 정의를 이용해 재귀 함수 구현
  • 기본 부분(Basis Part), 유도 부분(Inductive Part)로 구성
    • 기본 부분 : 기저 조건(재귀를 종료할 조건)
    • 유도 부분 : 실행 부분
  • 반복 구조에 비해 간결하고 이해하기 쉬움. (익숙하지 않으면 어렵게 느낄 수 있음.)
  • 함수 호출 : 스택 사용.
    • 재귀 호출 -> 반복적인 스택 사용 : 상황에 따라 메모리 및 속도에 성능저하 발생

• 재귀와 반복

  	재귀	반복
  종료	재귀 함수 호출이 종료되는 베이스 케이스	반복문의 종료 조건
  수행 시간	(상대적)느림	빠름
  메모리 공간	(상대적)많이 사용	적게 사용
  소스 코드 길이	짧고 간결	길다
  소스 코드 형태	선택 구조(if..else)	반복 구조(for, while)
  무한 반복시	스택 오버플로우	CPU 반복해서 점유

  • 재귀적 구현이 간단한 경우가 많다.
  • 일반적으로 재귀적 알고리즘은 반복 알고리즘보다 더 많은 메모리와 연산 필요.
  • 입력 값이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다.

1. 피보나치 수열

• 피보나치 수열 : 두 수의 합을 다음 항으로 하는 수열.
• 피보나치 : 반복 구현.
  • n회의 반복으로 계산 완료.

// 반복
int n = 10;
int f0 = 0;
int f1 = 1;
int fn = 0;

for(int i = 2; i <= 10; i++){
	fn = f0 + f1;
    f0 = f1;
    f1 = fn;
}

• 피보나치 : 재귀 구현.
  • 엄청난 중복 호출이 존재
    • fibo(7) : fibo(6) + fibo(5)
    • fibo(6) : fibo(5) + fibo(4)
    • fibo(5) : fibo(4) + fibo(3)
    • n이 7인 경우 5, 4 등 같은 입력으로 호출되는 경우가 있다.
    • 한 번 호출되었다면 메모리에 저장해두어 사용하는 것이 효율적.(메모이제이션, memoization)

fibo(n){
	if (n < 2) return n;	// 기본 부분(기저 조건)
    else return fibo(n-1) + fibo(n-2);	// 유도 부분
}

메모이제이션(memoization) : 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장하여 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술. 동적 계획법의 핵심.

2. 하노이 탑

• 하노이의 탑 게임은 세 개의 기둥과 서로 다른 크기의 N개의 원판으로 구성.
• 원판을 세 번쨰로 모두 옮겨야 성공.
• 원판을 옮길 때 반드시 한 개씩 옮길 수 있고 두 번째 기둥을 이용할 수 있음.
• 옮기는 과정에서 절대로 큰 원판이 작은 원판 위에 놓이지 않아야 한다.

public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int num; //원판 갯수
		num=scanner.nextInt();
		hanoi('A','B','C',num);
	}
   
	static int count = 0;
	public static void hanoi(char from,char temp,char to,int num){//from -> to 로 원판num이 이동
		if(num==0)
			return;
		hanoi(from,to,temp,num-1);
		System.out.printf("%d. %c에서 원판%d을(를) %c로 이동\n",++count,from, num, to);
		hanoi(temp,from,to,num-1);
	}