Recursion : 순환
- 자기 자신을 호출하는 함수
- 재귀함수
void func(...) {
...
func(...);
...
}
public class Code01 {
public static void main(String[] args) {
func();
}
public static void func() {
System.out.println("Hello...");
func();
// 무한루프 발생
}
}
적절한 구조 (return) 을 가지고 있다면 무한루프에 빠지지 않는다.
Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. (return)
Recursive case : recursion을 반복하다보면 결국 Base case에 수렴해야 한다.
public class Code02 {
public static void main(String[] args) {
int n = 4;
func(n);
}
public static void func(int k) {
if (k <= 0) { // Base case
return;
} else {
System.out.println("Hello...");
func(k - 1); // Recursive case
// 무한루프 발생X
}
}
}
public class Code03 {
public static void main(String[] args) {
int n = 4;
int result = func(n);
System.out.println(result);
}
public static int func(int k) {
if (k <= 0) {
return 0;
} else {
return n + func(k - 1);
}
}
}
/*
Factorial : n!
0! = 1
n! = n * (n - 1)!
*/
public static int factorial(int n) {
if (n == 0) { // Base case
return 1;
} else {
return n * factorial(n - 1); // Recursive case
}
}
// x의 n제곱 계산
public static double power(double x, int n) {
if (n == 0) { // Base case
return 1;
} else {
return x * power(x, n - 1); // Recursive case
}
}
// Fibonacci Number (피보나치)
public static int fibonacci(int n) {
if (n < 0) { // Base case
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
}
//최대공약수 : Euclid Method
public static int gcd(int m, int n) {
if (m < n) { // swap m and n
int tmp = m;
m =n;
n = tmp;
}
if (m % n == 0) { // Base case
return n;
} else {
return gcd(n, m % n); // Recursive case
}
}
출처 : 영리한 프로그래밍을 위한 알고리즘 강좌(인프런) - 권오흠 https://inf.run/6QzJX