[algo] 재귀함수란?

재귀함수

자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 재귀라고 함
처음 불렸던 함수와 그 안에서 부른 함수, 그 안의 안에서 부른 함수 다 다른 함수

ex.

• 1은 자연수입니다. <= 자기 자신
• 어떤 자연수의 바로 다음 수도 자연수입니다. <= 다시 자기 자신을사용

ex. 팩토리얼 구하기

def factorial(n: int) -> int:
    """양의 정수 n의 팩토리얼을 구하는 과정"""
    if n > 0: # 재귀함수 문제 풀이의 경우 반드시 재귀 함수의 종료조건을 명시해야!!
        return n * factorial(n - 1)
    else:
        return 1

가장 중요한 건 무엇이 반복되는지 봐야!!

반복되고 무엇이 바뀌는지 봐야!

재귀함수의 종료 조건

재귀함수의 경우 반드시 종료 조건을 명시해야 함!!!
제대로 명시하지 않으면 함수가 무한히 호출될 수 있음!

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

recursive_function(1)

# 최대공약수 (유클리드 호제법)
def gcd(a, b):
    if a % b == 0: # 재귀함수의 종료 조건 (a를 b로 나눴을 때 나머지가 0일 때 return을 실행
        return b
    else:
        return gcd(b, a % b) # return을 실제로 실행하지 않고 gcb() 재귀함수 호출
print(gcd(192, 162))