재귀와 귀납적 사고

어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다. 

 

재귀 구조 예시

수열

 

등차 수열

seq(n):
	if n = 1:
		return 1
	else:
		return seq(n-1) + 5

※반복해서 호출하는 재귀 알고리즘은 끝나기 위해서 반드시 경계 조건을 가지고 있어야한다. 위 알고리즘에서는 if n = 1이 경계조건이다. 

 

피보나치 수열

fib(n):
	if n=1 or n=2:
		return 1
	else:
		return fib(n-1) + fib(n-2)

※재귀 알고리즘의 사용은 문제를 해결하는데 유용할 수 있지만, 잘못 쓰면 치명적일 수 있다. 위에 예시에서 n이 커질수록 걸리는 시간이 매우 증가하게 된다. 이는 한번 계산했던 결과들을 다시 사용하지 못하고, 계속 호출하는 중복을 일으키기 때문이다. 

 

하노이 탑

a,b,c 3개의 기둥이 있고, 기둥 a에 넓이가 서로 다른 n개의 원반이 있을 때, 특정 규칙을 만족하면서 n개의 원반을 기둥 b로 옮기는 문제이다.

• 규칙
  • 원반은 한 번에 하나씩 옮길 수 있다.
  • 큰 원반이 작은 원반 아래에 놓여 있어야 한다.
• 알고리즘
  • 맨 아래 원반을 제외한 n-1개의 원반을 기둥 c로 옮긴다.
  • a에 있는 원반을 b로 옮긴다.
  • c에 있는 n-1개의 원반을 b로 옮긴다. 

move(n,a,b,c):
	if(n>0):
		move(n-1, a, c, b)
		a -> b
		move(n-1, c, b, a)