Java 코딩테스트 준비하기 - 재귀(Recursion) -

 

재귀란 자기자신을 호출하는것을 말합니다.

재귀함수란 자기자신을 호출하는 함수를 말합니다
재귀함수는 크게 Base case아 Recursive case로 구분이됩니다.

간단한 예로 Factorial를 살펴볼 수 있습니다.

첫번째 경우는 Base case로 보고 두번째 경우를 보면 n!을 위해 다시 (n-1)! 을 사용하게 되는 Recursive case로 볼 수 있습니다.

실행되는 것을 개념적으로 살펴보겠습니다.
함수들은 스택 메모리에서 실행이 됩니다.

메인에서 만약에 factorial(3)을 실행했다고 하면 첫번째 base case에 해당하지 않고 두번째 케이스에 해당하기때문에Factorial(2)가 실행이 되고 반복적으로 실행이 되어 factorial(0) 이 실행이되 면 비로소 base 케이스에 해당하기 때문에 
결과가 리턴이 되어서 해당 자리에 알맞은 값들로 반환이 됩니다.

그럼 재귀호출을 활용해서 Flood fill 알고리즘을 살펴보겠습니다
N의 값이 주어지고 배열의 값이 입력되고 시작위치가 주어질 것입니다.
벽을 만날 때까지 1을 입력해주면 됩니다.

이중for문을 이용해서 값들을 입력 받고

Fill이라는 메서드를 만들어 볼 것입니다.

배열의 범위보다 크다고 하면 모두 return을 할 것이다. 이부분이 base case에 해당합니다.
또한 0이 아니라면 return을 할 것이다. 이 두 부분이 base case에 해당하게 됩니다.

상하좌우의 경우를 모두 재귀호출 해주시면 됩니다. 이 부분이 Recursive case에 해당하게 됩니다.