재귀(Recursion)함수란?
특정 함수 내에서 직접 또는 간접적으로 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다.
문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식입니다.
일반 반복문을 통해 구현 가능한 기능은 재귀 함수를 통해 구현이 가능하며
반대로 재귀 수로 구현 한 기능을 반복문으로 구현이 가능합니다.
재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 반드시 종료 구간이 되는
Base Case를 생각하며 코드를 구현해야 합니다.
5! = 5 X 4 X 3 X 2 X 1
4! = 4 X 3 X 2 X 1
3! = 3 X 2 X 1
===> 5! = 5 X 4! ==> 5 X 4 X 3! --- !이 !를 호출
public class Recursion_Test {
public static void main(String[] args) {
Function ( );
}
public static void Function( ) {
System.out.println("반갑습니다");
Function( );
}
}
▶Function 이라는 Method를 정의하였습니다.
해당 함수의 기능은 "반갑습니다"를 호출하고 다시 자기 자신을 호출하고 있습니다.
해당 소스에서 문제는 자기 자신을 호출만 하고있지 함수 영역이 종료되는 구간이 없기 때문에
"반갑습니다"가 계속 출력되는 무한 루프에 빠지게 됩니다.
public class Recursion_Test {
public static void main(String[] args) {
Function ( 3 );
}
public static void Function(int num) {
if(num == 0) {
return;
} else {
System.out.println("반갑습니다");
Function(num - 1 );
}
}
}
▶Function Method는 매개변수 num을 받고 if 구문에 의해 분기가 되고 있습니다.
매개변수 값이 0일 경우 return을 하고 0이 아닐 경우 "반갑습니다"를 출력하고 num -1에 해당하는 값을 매개변수로 전달하고 있습니다.
여기서 num의 값이 0일 경우 return을 하게 되는 구문이 이 재귀 함수의 Base Case 구간이 됩니다.
즉,
public class PlusFunction {
public static void main(String[] args) {
HelloWorld(5); // HelloWorld 출력 메서드 호출
}
// HelloWorld 출력 메서드 선언
public static void main HelloWorld(int n) {
// n이 0인 경우 retrun
if(n == 0);
retrun;
System.out.println("HelloWorld"); // HelloWorld 출력
HelloWorld(n-1); // 재귀함수 시작
}
}
n이 0이 될 때 메서드를 끝 냅니다.
함수를 호출 할 때마다 n을 1씩 빼줘서 재귀 함수를 종료하게 만들어줍니다.
1부터 n까지의 합 구하기
Return에서 N+= 재귀함수를 호출하여 1부터 N까지의 합계를 구합니다
public class Recur {
public static void main(String[] args) {
System.out.println("1부터 5까지의 합은 :" + Function(5));
}
public static int Function(int num) {
if(num == 1) {
return 1;
} else {
return num + Function(num -1) ;
}
}
}
▶num이 1이면 그냥 1을 retunr을 하고 함수가 종료됩니다.
1이 아닐 경우 현재 num 값에 Function(num-1) 결과로 리턴되는 값을 더하여 리턴을 하게 됩니다.
풀이를 해보자면 5+1~4까지의 합니 되는 셈입니다.
매게 변수 값이 4가 넘어가게 되는 경우에는 4+1~3까지의 합이 됩니다.
즉,
public class PlusFun{
public static void main(String[] args) {
int N = 5;
System.out.println("1부터" + N + "까지의 합계 : " + PlusPlus(5)); // PlusPlus 출력 메서드 호출
}
// PlusPlus 출력 메서드 선언
public static int PlusPlus(int n) {
// n이 0인 경우 return
if(n == 0)
return = 0;
return n += PlusPlus(n-1); // 재귀함수 시작
Return 에서 N += 재귀함수를 호출하여 1부터 N까지의 합계를 구해줍니다
피보나치 수열구하기
피보나치 수열이란 n번째 숫자와 n1번째 숫자를 더한 값이 n2번째 숫자로 나타나는 수열이며
처음 여섯항은 각각 1, 1, 2, 3, 5, 8 .... 이다. 편의상 0번째 항을 0으로 두기도 한다.
기본 생성 규칙은 처음 두항의 숫자는 1입니다. 그래서 세번째 항은 기본적으로 1+1의 값인 2가 됩니다.
이런 규칙으로 네번째항은 두번째 항과 세번째 항의 숫자를 더한 1+2의 값으로 3이 됩니다.
public class Fibonacci {
public static void main(String[] args) {
int a1 = 1;
int a2 = 1;
int a3;
System.out.println(a1);
System.out.println(a2);
for(int i=1; i<=8; i++) {
a3=a1+a2;
System.out.println(a3);
a1=a2;
a2=a3;
}
}
}
즉,
public class FibonacciFunction {
public static void main(String[] args) {
int n = 10;
for(int i = 0; i < n; i++) // 피보나치 수열 출력
System.out.print(Fibonacci(i) + " ");
}
// 피보나치 수열의 결과를 구하는 메서드 선언
public static int Fibonacci(int n) {
if(n == 0)
return 0;
if(n == 1 || n == 2)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
이런식으로 N = (N-1) + (N-2) 이 계속해서 나오도록 해줍니다.
배열에서 최대값 찾기
재귀 함수를 응용 배열에서 최대값을 찾는 매서드입니다.
public class ArrayFunction
public static void main(String[] args) {
// 배열의 최대값을 가져온다
int arr[ ] = {0, 80, 60, 40, 20, 100} ;
System.out.println(ArraySort(arr,4));
}
// 크기가 N인 경우 최대값을 가져오는 메서드 선언
public static int ArraySort(int[ ] a, int n) {
int x;
if(n == 1)
return a[0];
else
x = ArraySort(a, n-1);
if(x > a[n-1])
return x;
else
return a[n-1];
}
}
'JAVA' 카테고리의 다른 글
| [Java] 수업 정리 20 은행계좌 프로그램 (24.11.19) (1) | 2024.11.24 |
|---|---|
| [Java] 수업 정리 19 (24.11.19) (0) | 2024.11.24 |
| [Java] 수업 정리 17 메소드(Method), 리턴(return) (24.11.19) (0) | 2024.11.24 |
| [Java] 수업 정리 _ 16 (24.11.12) (0) | 2024.11.14 |
| [Java] 수업 정리 _ 15 (24.11.12) (1) | 2024.11.14 |