재귀 함수가 반복문보다 느린 이유와 해결 방법을 서술하시오.

이유 : 함수 호출과 복귀를 하기 위한 Context Switching 비용이 발생하기 때문에 속도가 상대적으로 느려집니다. 즉, 오버헤드가 발생하여 속도 저하가 발생함.

 

해결법 : 꼬리 재귀 

 

func 팩토리얼(n, ans) {
  if n == 1 {
    return 1
    }
  return 팩토리얼(n-1, ans + n)
}

func 팩토리얼(n) {
  if n == 1 {
    return 1
    }
  return n + 팩토리얼(n-1)
}

위에가 꼬리재귀를 사용한 코드이며 밑이 꼬리재귀가 없는 코드이다.

 

얼핏보면 비슷해 보이지만 return을 할 때 함수의 호출부분에서 연산이 들어가는지 아닌지가 가장 큰 차이점이다. 

꼬리재귀를 사용하면 함수한테 추가적인 연산을 바라지 않기에 컴파일러가 스택의 문제를 선형으로 바꿔서 처리해 주기때문에 빨라진다.

 

단점으로는 컴파일러가 꼬리재귀에 대한 최적화를 지원해줘야 한다는 것이다.(Xcode는 지원한다.)