Page tree
Skip to end of metadata
Go to start of metadata

1. 재귀 함수(Recursive Function)

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미합니다.

def recursive_function():
	print('재귀 함수 호출')
	recursive_function()

recursive_function()


위 코드를 실행하면 출력을 계속 실행(스택이 꽉 차거나 언어 차원에서 최대 recursive call까지 제한됨)합니다.

종료 조건

재귀 함수를 사용할 때 가장 중요한 것은 종료 조건입니다.

def recursive_function(i):
	if 100 == i:
		return
	print('재귀 함수 호출')
	recursive_function(i + 1)

recursive_function(1)

위의 예제에서 처럼 i의 크기로 종료 조건을 넣어 종료하도록 하였습니다.


2. 백트래킹

백트래킹이란 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(backtrack)해 정답을 찾아가는 알고리즘으로 제약 충족 문제(Constraint Satisfaction Problems)에 유용합니다.

제약 충족 문제라는 말이 어렵지만 다음과 같이 이해하면 됩니다. 백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만입니다. 모든 경우의 수를 모두 찾는 것보다 ‘경우에 따라' 훨씬 빠를 수 있습니다.

왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문입니다.

백트랙킹은 DFS의 한 범주 안에 속하지만 전부다 탐색하는 것이 아닌 조건이 만족하는 곳만 탐색해서 더 빠르게 결과를 찾아내는 장점이 있습니다.


3. 오늘의 문제


  • No labels