recursive(1)

 

Recursion

-        자기 자신을 호출하는 함수(메서드)

-        통제를 통해 무한루프에 빠지지 않게 할 수 있다

 

무한통제 방지 구조

-        적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다 -> base case

-        Recursion을 반복하다보면 결국 base case로 수렴해야한다

 

대표적인 예시

1)     팩토리얼

2)     피보나치수열

3)     최대공약수

M>=N인 두 양의 정수 M과 N에 대해서 M이 N의 배수이면 gcd(M,N) = N이고, 그렇지 않으면 gcd(M,N) = gcd(n,M%N)이다.

코드)

Public static 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);
}
}

 

Recursion 응용

1)     미로찾기

-        이미 방문한 위치와 방문하지 않은 위치를 남겨야함

-        현재 위치가 출구이거나 인접한 곳에서 출구로 갈 수 있는 길이 있어야함

 

0 -> 길

1-> 벽

2-> 가봤지만 목표지점까지 갈 수 없는 곳임이 확인된 곳

3-> 가봤지만 목표지점까지 갈 수 있는지 없는지 여부 확인 X

2)Counting cells in a Bloob

-현재 픽셀이 image color가 아니면 0을 반환

-현재 픽셀이 Image color라면 현재 픽셀 카운트

-중복 카운트 되는 것을 방지하기 위해 다른 색으로 칠한다

-현재 픽셀에 이웃한 모든 픽셀들에 대해서 그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다

 

3) N queens Problem