알고리즘 - 재귀 함수(Recursive Function)

 

https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=831

<선행되어야 하는 자료구조 개념 - Recursive Function(재귀 함수)>

<재귀 함수의 사용법>

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

recursive_function()

- 이런 경우 오류가 난다. 한정된 크기만큼의 자원을 가지고 있는 컴퓨터에 계속해서 메모리를 쌓아 올리는 경우와 같기 때문이다. 

- 재귀에는 제한이 꼭 필요하다. 그 방법은 종료조건을 넣어주어 프로그램이 정해진 값을 반환해줄 수 있게 해야 한다.

 

 

<종료 조건을 명시한 재귀 함수>

#종료 조건을 명시한 재귀 함수

def recursive_function(i):
    #100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return
    
    print(i,'번째 재귀함수에서', i+1,'번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i,'번째 재귀함수를 종료합니다.')

recursive_function(1)

 

 

<반복문과 재귀를 이용한 팩토리얼 구현>

# 반복문을 이용해서 구한 팩토리얼
def factorial_iterative(n):
    result = 1
    for i in range(1,n+1):
        result *= i
    return result


# 재귀적으로 구현한 팩토리얼
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n-1)

print('반복적으로 구현한 팩토리얼: ',factorial_iterative(5))
print('재귀적으로 구현한 팩토리얼: ',factorial_recursive(5))

 

 

<최대공약수 계산(유클리드 호제법)>

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

print(gcd(192,162))

 

<재귀 함수 사용시 유의해야 할 사항>