재귀함수 이론

재귀함수도 cs 전공 수업 및 개인 알고리즘 공부할 때 이미 많이 배웠던 내용이니 간단하게 작성하겠다.

---

재귀함수 : 자기 자신을 다시 호출하는 함수.

• 일종의 스택 자료구조 안에 함수에 대한 정보가 차례로 담긴다. -> 컴퓨터 메모리는 한정적이기 때문에 무한이 함수를 호출하게 되면 문제가 발생할 수 있다.(스택오버플로우가 일어나는 예시 중 하나이다.)
• 의도적으로 무한히 호출하는 것이 아니라면 재귀함수의 종료 조건을 반드시 명시해야 한다.
• 코드가 훨씬 간결해질 수 있다.
• 모든 재귀함수는 반복문으로 동일한 기능을 구현할 수 있고, 반대로 모든 반복문은 재귀함수로 구현할 수 있다.

가장 흔한 예시인 팩토리얼의 코드를 구현해보겠다.

def factorial(n):
    # 재귀함수의 종료 조건이다. 이를 설정해주지 않는다면 factorial(n - 1)이 무한정 호출되기 때문에 factorial(-무한)까지 간다.
    # 0!과 1!은 1이다.
    if (n == 0 or n == 1):
        return 1
    # n이 0이나 1이 아니라면 n 곱하기 n - 1 팩토리얼을 리턴해준다.
    # 5! = 5 * 4!라고 생각하면 이해에 도움이 된다.
    return n * factorial(n - 1)
print(factorial(5)) # 120