재귀함수란?
함수가 자신을 다시 호출하는 구조로 만들어진 함수
탈출조건이 있어야 stack overflow를 방지할 수 있다.
재귀함수를 잘 푸는 방법?
재귀함수와 for문 비교
같은 일을 되풀이 할때에는 반복을 사용한다. for나 while등의 반복문을 사용하는 것으로 반복횟수를 가지고 있는 변수를 사용하여 일정횟수동안이나 어떤 조건이 만족될 때 까지 반복하도록 했다. 이러한 반복 구조는 문제를 간결하고 효율적으로 해결할 수 있다.
그러나 어떤 문제들은 반복을 사용하면 지나치게 복잡해지는 경우도 있다. 이런 경우에는 재귀가 매우 좋은 해결책이 될 수 있다. 예를 들면 트리 알고리즘을 들 수 있다. 트리의 순회나 노드의 삽입연산 등 재귀가 많이 사용되는데, 이들을 반복으로 구현하면 코드가 매우 복잡해진다. 따라서 재귀는 재귀적인 문제나 그러한 자료구조를 다루는 프로그램에 매우 효율적이다.
재귀함수를 구현하는 두가지 방법
def function(입력):
if 입력 > 일정값: # 입력이 일정 값 이상이면
return function(입력 - 1) # 입력보다 작은 값
else:
return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료
def function(입력):
if 입력 <= 일정값: # 입력이 일정 값보다 작으면
return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료
function(입력보다 작은 값)
return 결과값
하노이 탑 문제를 위 방법으로 구현해보자
def hanoi(n,start,mid,end):
if n == 1:
move.append([start,end])
else:
hanoi(n-1,start,end,mid)
move.append([start,end])
hanoi(n-1,mid,start,end)
move = []
n = int(input())
hanoi(n,1,2,3)
print((n**2)+1)
for i in move:
print(i[0], i[1])
def hanoi(n,start,mid,end):
if n == 1:
print([start,end])
return 0
hanoi(n-1,start,end,mid)
print([start,end])
hanoi(n-1,mid,start,end)
move = []
n = int(input())
hanoi(n,1,2,3)
print((n**2)+1)
분리해보니 둘의 차이는 잘 모르겠다..
재귀함수의 틀을 이해해서 응용하는 방식으로 공부해야겠당