[algorithm] 재귀 (feat. 하노이탑)

재귀 Recursion ?  자기 자신을 호출하여 문제를 해결하는 프로그래밍
                               더 작고 더 간단한 하위문제로 분할됨 (즉, 전체중 일부 하위문제해결법을 가지고 전체문제를 해결함)

나의 경우에 재귀를 떠올릴때면 ? 생각나는 그림이 엘리베이터에 탔을 때 
서로 마주본 거울 같은 느낌이다. 마주 본 거울은 계속 자신을 반사반사반사하면서 작아지고 어떤 한 점에 이른다. 

재귀를 쓸 때 생각 할 것들
1. Base case(종료조건)이 필요함 
2. 자기 자신을 호출해야 하고 하위 문제를 결합하여 전체에 대한 해결책을 얻어야 함 (recursive case)
3. 재귀 호출시 반드시 종료조건으로 수렴할 수 있도록 하는 조건 필요
4. 호출할때마다 콜스텍을 쓰기 때문에 메모리를 많이 소요한다는점 참고해서 반복문 쓸지 생각 잘하기

 

하노이의 탑 

• 하노이의 탑은 3개의 기둥이 있고, n개의 원반이 존재합니다.
• 맨 왼쪽 기둥에 있는 원반을 모두 맨 오른쪽 기둥으로 옮겨야 합니다.
• 원반은 하나씩만 옮길 수 있고, 크기가 작은 원반 위에는 크기가 큰 원반을 올려놓을 수 없습니다.

 

 

 

 

 

참고할 만한 글 ) 

https://ko.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursive-factorial