[자바 알고리즘]순환(Recursion)

순환(Recursion)이란?

--  자기자신을 호출하는 함수 --

 

void func(...)

{    

...

func(...);

...

}

위의 그림1-1을 보게되면 어떻게 될까?

계속 자기자신을 호출하기때문에 무한루프에 빠진다. 

그렇다면 Recusrsion은 항상 무한루프에 빠지게 될까?

우리가 Recursion을 어떻게 작성하냐에 따라서 무한루프에 빠지지않고 우리가 원하는 일을 하도록 만들수 있다.

아래 예제를 보자.

그림 1-2 예제의 실행결과는 어떻게 될것같은가...

아마도 Hello 가 4번 출력되는것을 볼수 있을것이다. 

***Recursion이 항상 무한 루프에 빠지는 것이 아님 ***

Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.(func())

Recursive case :  recursion을 반복하다보면 결국 base case로 수렴해야한다. (func(k-1))

그렇다면 무조건 Recursive case가 있으면 무한루프에 빠질까?  

예를들어 func(k+1)이 된다면 무한루프에 빠지게 될것이다. 

그래서 단순히 base case가 존재한다는 것으로 무한루프에 안빠지는것이아니라 recursice case 를 통해서 recursion이 반복다보면

 결국 base case로 수렴되서 종료된다면 무한루프에 빠지지 않는다. 

예제)

public class Hi {

public static void main(String[] args) {

int result = func(4);

}

public static int func(int n) {

if (n == 0)

return 0;

else

return n + func(n - 1);

}

}

이 함수가 하는일은?

<0~4까지의 합>

순환(Recursion)를 이용하여 다양한 알고리즘을 해결할수 있다.

아래소스는 Recursion을 이용한 알고리즘들이다.

	
int factorial(int n)
{
 if (n==0)
 return 1;
 else
 return n*factorial(n–1);
}


double power(double x, int n) {
 if (n==0)
 return 1;
 else
 return x*power(x, n–1);
}





int fibonacci(int n) {
if (n<2)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}





double gcd(int m, int n) {
if (m<n) {
int tmp=m; m=n; n=tmp; 
}
if (m%n==0)
return n;
else
return gcd(n, m%n);
}