[Algorithm] Recursion
in Computer Science on Algorithm
Recursion 재귀
- 정의 단계에서 자신을 재참조 하는 함수
- 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식
- 재귀 호출이나 되부름 이라고도 함
재귀 함수 특징
- 무한 루프 방지를 위해 함수가 끝날 때 까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다는 부분을 인지하고 작성
- 파이썬에서 재귀 함수는 한번에 호출되는 정도가 1000회 이하가 되어야 함
대표적인 재귀 함수 예시
def factorial(n):
if n <= 1:
return n
else:
return n * factorial(n-1)
def fibonacci(n):
if n < 2:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
def gcd(m, n):
if m < n:
m, n = n, m
if m % n == 0:
return n
else:
return gcd(n, m%n)
유클리드 호제법
두 자연수 m, n에 대하여 (m > n) m을 n으로 나눈 나머지를 l이라 했을 때, m과 n의 최대공약수는 n과 l의 최대공약수와 같다는 성질
