거울 속에 다시 거울이, 다시 거울 속에 거울이 비춰지고 있다.
갑자기 그게 뭐..

오늘 공부할 재귀가 잘 나타난 사진이다.

재귀

재귀 는 자기 자신을 포함하고 다시 자기 자신을 사용하여 반복되는 구조이다.

✅ 프로그래밍에서는 재귀 호출을 통해 재귀 함수로 사용

재귀를 효과적으로 사용하면 프로그램을 간결하고 효율성 좋게 작성할 수 있다.

재귀 함수 구조

재귀 함수는 반복적으로 자기 자신을 호출하는 구조를 가졌기 때문에 무한 루프에 빠질 위험이 있다.

재귀 함수 작성

• (재귀 종료 조건)
• 재귀
• 내부 진행 코드

따라서 재귀 함수를 쓸 때에는 상단에 종료 조건을 필수적으로 명시해,
무한 루프에 빠지지 않도록 한다.

종료 조건에 해당하지 않을 경우 수행할 재귀를 명시한다.

재귀 함수는 함수 내에서 자기 자신을 호출한 후
해당 함수의 종료 조건이 충족될 때까지 함수 호출 이후의 명령문이 시행되지 않는다.

[이미지 출처 : 플레이데이터 알고리즘 특강, 재귀]

재귀 함수의 대표 예시

1. 팩토리얼

재귀를 사용하는 대표적인 예로 팩토리얼 문제가 있다.

팩토리얼 n!의 정의 (n은 양의 정수)

• 0! = 1
• n > 0 이면 n! = n x (n - 1)!

이러한 정의를 factorial() 함수로 구현해보면 다음과 같다.

def factorial(n)
    if n > 0:
        return n * factorial(n - 1)
    else:
        return 1

2. 피보나치 수열

n = int(input())

def Fibonacci(n: int):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n - 2)
    
print(Fibonacci(n))