[딩코딩코 2025 코딩테스트 필수 알고리즘] - 7. 재귀함수

본 글에 사용된 코드와 이미지의 일부는
딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp\
​

---

재귀함수

재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.
이것을 함수에 적용하면 바로 자기 자신을 호출하는 함수가 된다.

그렇다면, 이런 재귀 함수를 왜 사용하는 걸까?
바로, 재귀 함수를 이용해서 간결하고 효율성 있는 코드를 작성할 수 있기 때문이다.

예시를 통해 살펴보자.

Q. 60에서 0까지 숫자를 출력하시오.

def count_down(number):
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)

코드를 돌려보면 끝도 없는 반복으로 인한 에러가 발생한다.

재귀함수는 반드시 빠져나가는 지점을 명확히 해줘야 무한 루프에 빠지지 않게 된다.

무한 루프에 빠지지 않게 위 코드를 고쳐보자.

def count_down(number):
    if number < 0:         # 만약 숫자가 0보다 작다면, 빠져나가자!
        return

    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)

다음과 같이 탈출 조건을 만들어줌으로써 재귀 함수의 반복을 멈출 수 있다.

예제

재귀함수의 대표적인 문제인 팩토리얼 문제를 풀어보자.

팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다.

3! = 3 * 2 * 1 = 6

즉, Factorial(n) = n * Factorial(n-1) , Factorial(n-1) = (n-1) * Factorial(n-2) 의 구조이다.

코드로 살펴보자.

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

print(factorial(60))