[python] 재귀 함수

1. 재귀 함수란?

 재귀 함수 (Recursive Function) 란 자기 자신을 다시 호출하는 함수를 의미한다. 아래의 그림은 '재귀 함수 호출' 이라는 문자열을 출력하는 함수를 정의하고, 그 함수를 다시 불러오는 형태의 재귀 함수를 만든 것이다.

 

 재귀 함수를 문제 풀이에서 사용하는 경우, 반드시 재귀 함수의 종료 조건을 입력해 주어야 한다. 그렇지 않으면, 위의 출력 값처럼 함수가 무한히 호출될 수 있다.

 

 아래의 예시는 i == 20 이라는 종료 조건을 준 예시이다.

2. 최대 공약수 계산 : 유클리드 호제법 예제

유클리드 호제법은 두 자연수 A, B에 대하여 ( A > B ) A를 B로 나눈 나머지를 R 이라고 했을 때, A와 B의 최대 공약수는 B와 R의 최대공약수와 같은 것을 이용하는 알고리즘이다. 이를 바탕으로 구현한 예제는 아래와 같다.

 

x , y 입력을 받고 그 두수의 최대 공약수를 출력해주는 재귀 함수 코드를 작성

3.  재귀 함수의 활용

 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다. 하지만 코드가 이해하기 어려울 수 있기 때문에, 주석을 자세히 적어서 다른 사람이 봤을 때 이해하기 쉽게 작성하는 것이 좋다.

 

 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다. 따라서, 상황에 맞게 재귀 함수 또는 반복문을 사용하는게 좋다. 

 

 컴퓨터가 함수를 연속적으로 호출을 하게 되면 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 된다. 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.