5. Recursion(재귀)

학기가 시작되면서 블로그 포스팅을 하기가 너무 빡세다... 해서 수업시간에 배운 자료구조 및 알고리즘들을 조금씩 틈을 내서 포스팅 해 보고자 한다.

 

오늘은 재귀(recursion) 알고리즘에 대한 포스팅이다. 재귀는 함수 안에 함수를 다시 호출하여 반복하는 알고리즘이다. 구현 하기가 어렵지만 구현을 성공하면 생각보다 길이도 짧으면서 다른 사람들이 보기에도 쉬운 멋진 알고리즘이다.

 

대표적인 재귀 알고리즘 3가지를 소개해 보고자 한다.

 

#1. 피보나치 수열

 

  

우리가 흔히 알고있는 피보나치 수열은 0 1 1 2 3 5 8 13 21 34 55 69 124 이런식으로 n-2와 n-1의 자리를 더한 값을 n값으로 하는 알고리즘이다. 위의 재귀함수로 간단하게 구현할 수 있다.

 

 

#2. 하노이 탑

 

 

하노이 탑은 구글에서 "하노이 탑"으로 검색하면 손 쉽게 어떤 원리인지 알 수 있을 것이다. 위와 같은 재귀 알고리즘의 대표적인 문제로, 재귀를 사용하지 않는다면 엄청나게 복잡한 문제가 될 수 있지만 재귀함수를 사용하여 반복되는 패턴만 파악하면 간단하게 해결할 수 있다.

 

 

#3. 이진검색 기법 구현

 

 

이전에 선형 검색과 이진 검색 알고리즘에서 소개했던 이진검색 알고리즘을 재귀를 사용하여 구현해 보았다. for문이나 while문을 사용하여 반복문으로 검색 알고리즘을 구현할 수 있지만, 재귀를 사용해서도 어렵지 않게 구현할 수 있다.

이 코드를 통해 알 수 있는 재귀의 특성이 하나가 있다.  바로 종료 지점을 기록해 주어야한다는 점!!!

위 1,2번의 코드는 종료가 딱히 필요가 없는 코드여서 구현을 하지 않았지만, 재귀의 가장 큰 특성중 하나는 반드시 끝나는 지점을 기록해 주어야 한다는 점이다. 그렇지않으면 무한루프를 돌 수 있는 알고리즘이므로 반드시 끝을 정해주어야 한다.