재귀 함수

재귀 함수(Recursive Function)

• 함수가 직접 또는 간접적으로 자기 자신을 호출하는 프로세스를 말합니다
• 자기 자신을 반복적으로 부르기에 종료 조건을 제대로 생각하지 않고 구현하면 스택오버플로우가 발생할 확률이 매우 높습니다.
• 재귀 호출: 한 메서드가 실행과정 중 자기 자신을 호출한 경우

def factorial(n):
    if (n == 1): #종료조건
        return 1
    
    return n * factorial(n - 1) #자기 자신 호출

가장 대표적인 재귀함수를 이용한 예시는 팩토리얼이다.

재귀 함수는 왜 쓰는 것일까?

사실 재귀는 반복문과 같은 역할을 하는 것이 아닌가? 왜 단순한 반복문이 아닌 복잡한 생각을 거치는 재귀함수를 사용하는 것일까?
라는 생각이 저는 들었습니다.(다른 분들은 어떨지 모르지만!)
그래서 찾아보게되었습니다.

• 재귀적 사고는 프로그래밍에서 굉장히 중요하고, 문제를 잘게 부수는데 도움을 준다
• 재귀함수는 반복문보다 가독성이 높다.
• 재귀를 사용하는 경우 복잡한 코드가 심플한 코드가 될 수 있다.
• 그러나 재귀함수는 메모리를 많이 차지해서 성능이 떨어지는 위험이 있을 수 있으므로 조심해서 사용해야한다.

꼬리 재귀 (tail call recursion)

재귀에 대해 조사하다가 발견하게 된 내용입니다.
재귀함수의 문제점 중 1개가 메모리를 많이 차지하는 것이었는데 꼬리 재귀가 이를 해결할 수 있다고 합니다.

# 재귀 버전
def factorial(n):
    if (n == 1):
        return 1
    
    return n * factorial(n - 1)


# 꼬리 재귀 버전
def tail_factorial(n , total):
    if n == 1:
        return 1
    
    return tail_factorial(n - 1, n * total)

정확하게 이해는 못했지만 이해한대로 얘기해보자면 꼬리 재귀는 return 부분에 연산이 없어야하는 것 같습니다.
이렇게 구현할 경우 컴파일러가 꼬리 재귀 최적화를 지원하여 재귀함수를 해석해서 반복문으로 변경해서 실행하기 때문에 스택 오버 플로우를 해결할 수 있다고 합니다.
자세한 내용은 더 공부를 하고 깨달으면 적도록 하겠습니다.