<기본코드>
public class Chap_05 {
static int recursion1(int n) {
if (n == 1) {
return 1;
}
return 3 * recursion1(n - 1);
/*
n = 4
return 3 * recursion1(n - 1); 호출
3 x recursion1(3)
3 x recursion1(2)
3 x recursion1(1)
3 x return 1
3, 9, 27
*/
}
static int recursion2(int n){
if (n == 1){
return 1;
} else {
return n + recursion2(n-1);
}
}
static int recursion3(int n){
if (n < 3){
return 1;
} else {
return recursion3(n-2) + recursion3(n-1);
}
}
/*
n = 6
recursion3(4) + recursion3(5)
recursion3(4) = recursion3(2) + recursion3(3)
recursion3(3) = recursion3(1) + recursion3(2)
recursion3(5) = recursion3(3) + recursion3(4)
recursion3(4) = recursion3(2) + recursion3(3)
recursion3(3) = recursion3(1) + recursion3(2)
*/
public static void main(String[] args) {
// 점화식 -> 반복문, 재귀함수
System.out.println("== 점화식/재귀함수 연습1 ==");
// 1, 3, 9, 27, ... 의 n번째 수
int n = 4; //4번째 수
int result = 1;
for (int i = 0; i < n; i++) {
if (i == 0) {
result = 1;
} else {
result *= 3;
}
}
System.out.println(result); // n번째수 출력
/*
a1 = 3 x an
an+1 = 3 x an
*/
System.out.println("== 점화식/재귀함수 연습2 ==");
// 1, 2, 3, 4, 5, 6, ... 의 n번째 까지의 합
n = 5;
result = 0;
for (int i = 1; i < n + 1; i++) {
result += i;
}
System.out.println(result);
System.out.println("== 점화식/재귀함수 연습3 ==");
// 1, 1, 2, 3, 5, 8, 13, ...의 n번 째 수
n = 6;
result = 0;
int a1 = 1;
int a2 = 1;
if (n < 3) {
result =1;
} else {
for (int i = 2; i < n; i++) {
result = a1+ a2;
a1 = a2;
a1 = result;
}
System.out.println("result = " + result);
}
}
}
<연습문제>
(1)
public class Practice_05 {
static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
// Test code
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
}
}
(2)
// Practice2
// 최대공약수를 재귀함수로 구현하시오.
public class Practice_06 {
static int gcd(int a, int b){
if (a % b ==0){
return b;
} else {
return gcd(b, a%b);
}
}
/*
만약 gcd로 3과 5가 넘어오면,
처음 3을 5로 나눈 나머지가 0이 되지 않으니, return gcd(b, a%b) 실행
gcd(5, 3) -> gcd(3, 2) -> gcd(2, 1)
// 0이 나올때 값이 최대 공약수
gcd(5,3)
*/
public static void main(String[] args) {
// Test code
System.out.println(gcd(3, 5));
System.out.println(gcd(2, 6));
System.out.println(gcd(8, 12));
}
}