재귀

재귀

반복과 재귀

• 반복과 재귀는 유사한 작업을 수행할 수 있다.
• 반복은 수행하는 작업이 완료될 때까지 계속 반복
  • 루프(for/while, do-while구조)
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
  • 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다.
  • 재귀 함수로 구현

재귀함수

• 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수
• 일반적으로 재귀적 정의를 이용해서 재귀함수를 구현한다.
• 따라서, 기본부분(basic part)와 재귀의 끝과 유도 파트(inductive part)로 구성된다.
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다. 그러나, 재귀에 대해 익숙하지 않은 개발자들은 재귀적 프로그램이 어렵다고 느낀다
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다.
• 따라서, 재귀 호출은 반복적인 스택의 사용을 의미하며, 메모리 및 속도에서 성능저하가 발생한다

팩토리얼 재귀함수

• 재귀적 정의
  • Basic rule : N<=1인 경우, N=1
  • Inductive rule : N>1, n!= n * (n-1)
• n!에 대한재귀함수

   int factorial(int n//구해지는 값이 결정적 요인 바뀌는 값, 매개변수 설계){
   	if(n<=1)
       return 1;
   else
       return n*factorial(n-1);
   }
  

피보나치 재귀함수

• 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라 한다.
• 피보나치 수열의 i번째 값을 계산하는 함수F를 정의하면 다음과 같다.
• F0 = 0; F1 = 1
• Fi = Fi-1 + Fi-2 for i>=2
• 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있따.
• 피보나치 수를 구하는 재귀함수

  fibo(n)
   if(n <= 1) then
       return n;
   else
       return fibo(n-1) + fibo(n-2);
  end fibo(n)
  

• 단, 위의 예에서 피보나치 수를 구하는 함수를 재귀함수로 구현한 알고리즘은 문제가 있다.
• “엄청난 중복 호출이 존재한다”는 것이다.

Memoization

• 앞의 예에서 피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 O(n)으로 줄일 수 있다.

//memo를 위한 배열을 할당하고, 모두 0으로 초기화 한다.
//memo[0]을 0으로 memo[1]은 1로 초기화 한다.

fibo(n)
	if n>=2 and memo[n] is zero then
		memo[n] <- fibo(n-1) + fibo(n-2);
	return memo[n];
end fibo()  

반복 또는 재귀?

• 해결할 문제를 고려해서 반복이나 재귀의 방법을 선택
• 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽다
• 추상자료형(List, tree)등의 알고리즘은 재귀적 구현이 간단하고 자연스러운 경우가 많다.
• 일반적으로, 재귀적 알고리즘은 반복알고리즘보다 더 많은 메모리와 연산을 필요로 한다.
• 입력 값 n이 커질수록 재귀 알고리즘은 반복에 비해 배효율적일 수 있다.

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

하노이의 탑 문제

• 제약사항 * 원판 번호는 맨 위부터 1,2,3 순 부여
  • 기둥은 3개로 가정한다(기둥 번호는 왼쪽부터 1,2,3순으로 부여)
  • 시작은 N개의 원판이 1번 기둥에 쌓여져 있다
• 입력 * 원판 개수인 N을 입력 받는다.(1<=N<=10)
  • 원판 번호는 맨 위부터 1,2,3 순으로 부쳐
• 출력 * 옮겨지는 원판 번호 : 출발 기둥 번호 -> 목적 기둥 번호

public class Main{
	private static void hanoi(int n, int start, int temp, int dest){
		if(n==0) return;
		//자신의 위쪽의 n-1개의 원판 들어내기 : 임시기둥으로 옮기기
		hanoi(n-1,start,dest,temp);
		//자신의 원판 옮기기 : 목적기둥
		System.out.pritnln(n + ":" + start + ">" + dest);
		//들어냈던 임시기둥의 n-1개 원판 자신위에 쌓기 : 목적기둥으로 옮기기
		hanoi(n-1,temp,start,dest);
	}
	public static void main(String[] args{
		hanoi(3,1,2,3);
	}
}