[알고리즘] 1. 재귀 함수(Recursion)

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.

 

자기 자신을 계속해서 호출하다가, 일정한 조건이 만족되면 함수를 반환하여 결과를 도출한다.

 

컴퓨터 내에서 재귀 함수는 스택 자료구조와 동일하다. 함수를 계속 호출했을 때, 마지막으로 호출된 함수가 먼저 종료되어야 첫 함수가 종료된다.

 

아래는 재귀 함수의 대표적인 예시인 팩토리얼이다.

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

 

재귀 함수의 장점은 수학의 점화식을 표현한 코드여서 매우 간결한 표현이 가능하단 것이다.

단, 끝없이 재귀 함수가 반복되지 않도록 함수를 끝낼 수 있도록 조건을 만들어놓아야 한다.