자기 자신을 호출하는 함수 혹은 메서드(=재귀함수)
public class Code01 {
public static void main(String [] args){
func();
}
public static void func(){
System.out.println("Hello...");
func();
}
main에서 func()를 호출한다 -> "Hello..."를 출력한다 -> 다시 func()를 호출한다 ... -> "Hello..."를 호출한다
너무나도 당연하게 무한 루프
에 빠질 수 있다.
Q. recursion은 항상 무한루프에 빠질까?
public class Code02{
public static void main(String [] args){
int n = 4;
func(n);
}
public static void func(int k){ // 매개변수 k
if(k<=0) // 매개변수 0이하라면 (음수)
return; // 자기 자신을 호출하지 않는다(종료).
else { // 0보다 큰 경우(양수)
System.out.println("Hello...");
func(k-1); // 인자값을 1만큼 감소시켜준다.
}
}
}
무한루프에 빠지지 않기 위한 전제조건
Base case
: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
if (k<=0)
return;
Recursive case
: recusion을 반복하다보면 결국 base case로 수렴해야 한다.
func(k-1);
=> Base case
와 Recusive case
의 두 가지 전제조건이 성립되어야 무한루프에 빠지지 않는다.
public class Code01{
public static void main(String [] args){
int result = func(4);
System.out.print(result);
}
public static void func(int n){
if(n==0) // n=0이라면 합은 0이다.
return 0;
else {
return n+func(n-1);
// func(n-1)메서드를 호출하고 n만큼 더 해준다. 1~n가지의 합을 구한다.
// n이 0보다 크면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.
}
}
}
0! = 1
n! = n*(n-1)! n > 0
public static int factorial(int n)
{
if(n==0)
return 1;
else
return n*factorial(n-1);
}
X0 = 1
Xn = X*Xn-1 if n>0
public static double power(double x, int n){
if(n==0)
return 1;
else
return x*power(x, n-1);
}
f0 = 0
f1 = 1
fn = fn-1 + fn-2 n>1
public int fibonacci(int n){ // n이 음수가 아니라는 것을 가정했을 때
if(n<2)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}
public static int gcd(int m, int n){
if(m<n){ // m값이 n보다 작을 경우
int tmp=m; m=n; n=tmp; // m과 n을 swap한다
}
if(m%n==0) // m이 n으로 나누어서 떨어지는 값이 0이라면 최대공약수이다.
return n;
else // m이 n으로 나누어 떨어지지 않는다면, n값과 m을 n으로 나눈 나머지 간의 최대공약수와 동일하다.
return gcd(n, m%n);
}
=> m≥n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n이고, 그렇지 않으면 gcd(m,n)= gcd(n,m%n)이다.
Reference