[Swift알고리즘] 재귀함수란?

1. 재귀함수란?

재귀함수란, 내 자신을 반복해서 호출하는 함수이.

예를 들면,

func recursiveFunction() {
  recursiveFunction()
}

다음과 같이 recursiveFunction() 내에서 recursiveFunction()을 호출한다.

이 경우, recursiveFunction()함수는 재귀함수 이다.

하지만 재귀함수의 경우 보통은 원하는 값을 얻을때 까지 재귀를 반복한다.

예제를 통해 알아보자.

2. 재귀함수 예제 - Factorial

일반적으로 팩토리얼을 함수로 표현한다면 다음과 같이 for문을 통해 작성할 것이다.

func facotorial(number : Int) -> Int {
  var result = 1
  for num in 1...number {
    result *= num
  }
  return result
}

하지만 재귀함수는 자신을 함수 내에서 호출하는 방식으로 구현해야 한다.

1! = 1, 2! = 2 x 1!, 3! = 3 x 2!, 4! = 4 x 3!, …

팩토리얼은 다음과 같이 표현될 수 있으므로 재귀함수로써 구현한다면 아래와 같다.

func facotorial(number : Int) -> Int {
  if number == 0 {
        return 1
    } else {
        let num = number * factorial(number: number-1)
        return num
    }
}

이런 식으로 마지막 실행이 1!이 될 때까지 반복실행한다.

재귀함수는 함수 내에서 자신을 반복실행 하므로 팩토리얼 함수에서의 number == 0과 같이 함수반복을 멈추고 탈출할 수 있는 조건이 필요하다.

3. 마무리

백준의 단계별로 풀어보기의 재귀단계를 시작하면서 재귀함수에 대해 알아보았다.

재귀함수의 메모리사용, 시간복잡도, 공간복잡도를 알고 싶다면 아래의 출처를 통해 알아가길 바란다.

출처 : https://babbab2.tistory.com/99