[Java] 점화식과 재귀함수

점화식(Recurrenct)

• 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식
  • 예) 피보나치 수열

 1, 1, 2, 3, 5, 8, 13, ...
 F1 = F2 = 1, Fn+2 = Fn+1 + Fn

재귀함수(Recursive Function)

• 어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식
• 종료 조건이 반드시 있어야 한다. 없는 경우 무한루프에 빠질 수 있다.

반환타입 함수이름(매개 변수) {
	종료 조건
     ....
	함수 이름(...)  -> 자기 자신을 호출
}

점화식 -> 반복문, 재귀함수

//1, 2, 3, 4, 5, 6, ... 의 n번째 까지의 합
//반복문
int n = 5;
int result = 0;
for (int i = 1; i < n + 1; i++) {
    result += i;
}
System.out.println(result);        //15 출력


//재귀함수
public int recursion(int n) {
	if(n == 1){
    	return 1;
    }
    return n + recursion(n - 1);
}



//1, 1, 2, 3, 5, 8, 13, ...의 n번 째 수(피보나치 수열)
//반복문
int n = 6;
int result = 0;
int a1 = 1;
int a2 = 1;

if(n < 3) {
	return 1;
} else {
	for(int i = 2; i < n; i++) {
		result = a1 + a2;
        a1 = a2;
        a2 = result;
	}
}
System.out.println(result);     //8 출력


//재귀함수
public int recursion3(int n) {
    if (n < 3) {
        return 1;
    }
    return recursion3(n - 2) + recursion2(n - 1);
}

재귀함수 Practice

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


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