[Algorithm] Recursion 이론 + 예제

❗Recursion이란?

함수가 자기 자신을 호출하는 프로그래밍 기법이다. 하나의 함수가 자신의 작업을 해결하는 과정에서 스스로를 다시 호출하여 문제를 반복적으로 해결하는 방식이다. 그래서 종종 복잡한 문제를 더 작은 문제로 나누어 해결할 때 사용한다.

 

❗ 재귀 함수의 구성 요소

1. 기본 조건 (Base Case)
   • 재귀 호출이 무한히 반복되지 않도록 하기 위한 종료 조건
   • 기본 조건이 만족되면 재귀 호출이 중단되고 함수가 결과를 반환하거나 종료됨
2. 재귀 호출 (Recursive Case)
   • 문제를 해결하기 위해 함수가 자기 자신을 호출하는 부분
   • 보통 이 과정에서 더 작은 크기의 문제로 재귀 호출이 이루어짐

 

❗예제

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

def func(k):
	if k == 0:
        return

    print(k, end=" ")
    func(k - 1)
    print(k, end=" ")

func(5)