재귀함수 알고리즘

재귀함수 ( Recursive Function)

• 자기 자신을 다시 호출하는 함수
• 파이썬에서는 최대 재귀 깊이가 존재함
• 재귀 함수 시작 부분에 종료 조건을 반드시 명시해야함

def recursive_function(i):
	if i == 100:
		return
    recursive_function(i+1)

재귀함수를 이용한 팩토리얼 구현 예제

n! = 1x2x3x4x...x(n-1)n
n! = n (n-1)!

def factorial_recursive(n):
	if n<=1:
    	return
        
    return n * factorial_recursive(n-1)

재귀함수를 이용한 유클리드 호제법 구현 예제

=> 최대공약수 계산

# a>b 일때
def gcd(a,b):
	if a%b == 0:
  		return b
    else:
    	return gcd(b, a%b)