재귀함수 (1)

• 자기 자신을 호출하는 함수

void func(...){
	...
	func(...);
	...
}

recursion이 항상 무한루프에 빠지는 것은 아니고 종료 조건을 알맞게 설정해주면 원하는 만큼 함수 호출이 가능하다.

적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. → 종료 조건

recursion을 반복하다면 결국 종료조건으로 수렴해야 한다.

• 1~N까지의 합

public static int func(int n){
	if(n == 0)
		return 0;
	else
		return n + func(n-1);
}

• 팩토리얼

0! = 1

n! = n x (n-1) ! (n>0)

public static int factorial(int n){
	if(n == 0)
		return 1;
	else n * factorial(n-1);
}

• xⁿ

x 0승은 = 1

x n승은 = x * x ^n-1 (n > 0)

public static double power(double x, int n){
	if(n == 0)
		return 1;
	else
		return x * power(x, n-1);
}

• 피보나치 수열

f0 = 0

f1 = 1

f(n) = f(n-1) + f(n-2) , (n>1)

public int fibonacci(int n){
	if(n < 2)
		return n;
	else 
		return fibonacci(n-1) + fibonacci(n-2);
}

• 최대 공약수 (유클리드 호재법)

m≥n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m, n) = n이고, 그렇지 않으면 gcd(m,n) = gcd(n , m%n)이다.

public static int gcd(int m, int n){
	if(m < n){
		int temp = m; 
		m = n;
		n = tmp;
	}
	if(m%n == 0)
		return n;
	else 
		return gcd(n, m%n);
}

• 유클리드 호재법 단순한 버전

gcd(p, q) = { p (q =0), gcd(q, p%q) }

public static int gcd(int p, int q){
	if( q == 0)
		return p;
	else 
		return gcd(q, p%q);
}

---

순환적으로 사고하기

수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.

• 문자열 길이 계산

if the string is empty
	return 0;
else
	return 1 plus the length of the string that
		excludes the first charater;

public static int length(String str){
	if(str.equals(""))
		return 0;
	else
		return 1 + length(str.substring(1));
}

• 문자열의 프린트

public static void printChars(String str){
	if(str.length() == 0)
		return;
	else{
		System.out.pritn(str.charAt(0));
		printChars(str.substring(1));
	}
}

• 문자열을 뒤집어 프린트

public static void printCharsReverse(String str){
	if(str.length() == 0)
		return;
	else{
		printCharsReverse(str.substring(1));
		System.out.print(str.charAt(0)); //출력을 나중에 해준다
	}
}

• 2진수로 변환하여 출력

public void printInBinary(int n){ //음이 아닌 정수 n을 이진수로 변환하여 인쇄한다.
	int (n < 2)
		System.out.print(n);
	else{
		printInBinary(n/2);  //n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후
		System.out.print(n%2); //n을 2로 나눈 나머지를 인쇄한다.
	}
}

• 배열의 합 구하기

public static int sum(int n, int[] data){
	if(n <= 0)
		return 0;
	else
		return sum(n-1, data) + data[n-1];
 }

• 데이터파일로 부터 n 개의 정수 읽어오기

public void readFrom(int n, int[] data, Scanner in){
	if(n == 0)
		return;
	else{
		readFrom(n-1, data, in);
		data[n-1] = in.nextInt();
	}
}

모든 순환 함수는 반복문(iteration)으로 변경 가능

그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능함

순환함수는 복잡한 알고리즘을 단순하게 알기쉽게 표현하는 것을 가능하게 함

하지만 함수 호출에 따른 오버헤드가 있음(매개변수 전달, 엑티베이션 프레임 생성 등)