재귀함수

재귀함수

스택을 함수에 적용시킨 개념이다. 자기 자신을 다시 호출하는 함수이다.

def recursive_function():
  print('재귀 함수를 호출합니다.')
  recursive_function()
recursive_function()

 그러나 위 코드처럼 재귀함수를 실행하면 무한 루프에 빠지게 되고 결국 재귀의 최대 깊이를 초과했다는 오류 메시지가 뜬다. 재귀함수는 컴퓨터 내부에서 스택을 통해 적재되기 때문에 메모리 한도치를 초과하게 되면 에러가 뜨는 것이다.

 

결국 재귀함수를 사용할 때는 다음과 같이 종료조건을 명시해주어야 한다.

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

 

 

두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로 재귀함수를 사용한 유클리드 호제법이 있다.

- 유클리드 호제법

두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다.

이 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

이를 코드로 표현하면 다음과 같다.

def gcd(a,b):
  if a%b==0:
    return b
  return gcd(b,a%b)

이처럼 재귀 함수는 수학의 점화식을 그대로 소스코드로 옮기기 때문에 반복문에 비해 더 간결한 코드를 얻을 수 있다. 그러나 종료조건을 명확히 해 무한루프에 빠지지 않도록 주의해야 한다.