[자료구조] 점화식과 재귀함수

1. 점화식

• 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식
• ex) 피보나치 수열
  • 1, 1, 2, 3, 5, 8, 13, ...
  • F1 = F2 = 1, Fn+2 = Fn+1 + Fn

2. 재귀함수

• 어떤 함수가 자기 자신을 다시 호출하여 작업을 수행하는 방식
• 반환타입 함수이름 (매개변수) { 종료 조건 ... 함수이름(매개변수) }
• 종료 조건 필수,  없으면 무한 루프에 빠짐

3. 코드

// 1, 3, 9, 27, ..., n번째 수
// 1. 점화식 -> 반복문
int n = 4;
int result = 1;
for (int i = 0; i < n; i++) {
	if (i == 0) {
    	result = 1;
    } else {
    	result *= 3;
    }
}

// 2. 재귀함수
private static int resursion(int n) {
	if (n == 1) {
    	return 1;
    }
    return 3 * recursion(n - 1);
}

// 팩토리얼 (재귀함수로 구현)
private static int factorial(int n) {
	if (n == 1) {
    	return 1;
    }
    return n * factorial(n - 1);
}

// 최대공약수 (재귀함수로 구현)
private static int gcd(int a, int b) {
	if(a % b == 0) {
    	return b;
    }
    return gcd(b, a % b);
}