[cs]재귀 함수

오늘 우연치 않게 나도 모르게 메서드 호출을 함수 안에서 했다. 어쩌다보니 재귀함수를 사용해서 나의 코드는 무한루프에서 빠져나오지 못하고 있었다...

재귀 함수는 자기 자신을 호출하는 함수로, 특정 문제를 작고 반복적인 작업으로 분해하여 해결하는 데 유용하다고 한다. 특히, 같은 작업을 반복해서 수행하거나, 큰 문제를 작은 하위 문제로 나누어 해결할 때 자주 사용된다.

• 예를 들어, 가장 많이 들어본 팩토리얼 계산을 통해 재귀 함수의 동작 이해해볼 수 있다.

• 팩토리얼은 정수 n에 대해서 n!=nx(n−1)x(n−2)x...x1로 정의된다.

func factorial(_ n: Int) -> Int {
    if n == 1 {
        return 1
    }
    return n * factorial(n - 1)
}

여기서 factorial 함수는 입력이 1일 때 멈추고, 그렇지 않으면 자기 자신을 호출하며 n에서 1씩 감소한 값을 곱한다. 이렇게 작은 문제로 쪼개어가는 방식으로 해결하는 것이 재귀 함수의 기본 개념이라고 한다.

# 재귀 함수의 장단점

• 장점:
  • 문제를 작은 단위로 나누어 간결하게 표현할 수 있다.
  • 특정 알고리즘에서 반복 구조 대신 재귀 구조를 사용하면 가독성이 향상된다.
  • 트리 구조나 그래프 탐색처럼 반복 작업이 필요한 알고리즘에서 유용하다.
• 단점:
  • 함수 호출이 중첩되므로 메모리 사용량이 증가한다.
  • 잘못된 종료 조건 설정 시 무한히 호출될 수 있어 스택 오버플로우를 발생시킬 위험이 있다.

# 재귀 함수의 종료 조건

재귀 함수에는 반드시 종료 조건이 필요하다. 종료 조건이 없으면 함수가 무한히 반복되어 프로그램이 멈추거나 오류가 발생할 수 있다. 종료 조건은 특정 상태가 되면 재귀 호출을 멈추고 결과를 반환하도록 한다.

• 예를 들어, 팩토리얼 계산에서 if n == 1은 종료 조건이며, 이 조건을 만족하면 더 이상 재귀 호출을 하지 않고 결과를 반환해서 함수가 종료된다.

# 재귀 함수의 활용 예시

• 피보나치 수열
• 하노이 탑 문제
• 그래프 탐색

# 결론

재귀 함수는 반복적이고 구조적인 문제를 해결하는 데 강력한 함수이다. 하지만 메모리 사용량이나 무한 루프의 위험을 줄이기 위해 적절한 종료 조건을 설정하고, 재귀가 필요한 상황에서만 사용하는 것이 중요하다. 그렇게 나는 탈출 조건도 없는 함수를 재귀함수로 받아와 계속해서 무한루프에 빠졌었던 것이다.