python/알고리즘 문제풀이

BFS와 DFS (2) / 재귀 함수

빛날희- 2021. 6. 28. 01:50

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다. 


▶ 재귀함수(Recursive Function)란?

자기 자신을 다시 호출하는 함수로 DFS와 BFS에 자주 활용되는 형식이다. 파이썬에서 재귀함수는 무한히 함수를 호출하다가 최대 재귀 깊이를 초과하게 되면 최대 재귀 깊이 초과메시지가 출력되며 함수실행이 종료된다. 따라서 반복문 대신 재귀함수를 사용하여 반복문을 사용하지 않고 코드를 반복할 수 있다

 

 

 

▶ 재귀함수의 종료조건

재귀함수 실행을 종료시키는 조건을 명시함으로써 특정 조건을 만족하면 함수가 종료되도록 설정해야한다. 그렇지 않으면 함수가 최대 재귀깊이까지 반복될 것이다. 

i가 10이 되었을 때 재귀함수 호출을 중단하도록 조건을 명시하였다. 재귀함수는 호출 될 때 메모리 내부에 스택구조로 쌓이기 때문에 함수가 종료될때 나중에 들어온 함수부터 차례대로 종료되는 문구를 출력한다. 

 

 

 

▶ 재귀함수의 활용 1 - 팩토리얼 계산

팩토리얼은 반복문을 통해서도 구현할 수 있지만 재귀함수를 호출하여 다음과 같이 구현할 수 있다. 

 

반복문 대신 재귀함수를 사용함으로써 코드가 더 간결해졌다. 

 

 

 

▶ 재귀함수의 활용 2 - 최대공약수 계산, 유클리드 호제법

두 개의 자연수에 대한 최대공약수를 구하는 활용법이다. 유클리드 호제법은 A를 B로 나눈 나머지 R에 대해 A와 B의 최대공약수와 B와 R의 최대 공약수가 동일하다는 명제로 부터 나왔다. 이를 재귀함수로 표현해볼 수 있다. 

 

 

▶ 정리

- 재귀함수는 점화식을 직관적이고 짧은 코드로 간결히 작성할 수 있다.

- 반복문을 이용하여 동일한 기능을 구현할 수 도 있으나 반복문이 더 유리한 경우도 있다.

- 재귀함수를 연속적으로 호출하면 메모리 내부의 스택 프레임에 쌓이기 때문에 스택 라이브러리 대신 재귀함수를 이용할 수 있다.