[알고리즘] 재귀함수(Recursion function), 꼬리재귀함수(Tail call recursion)

재귀함수란

- 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. 

 

- 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다.

 

- 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다.

 

재귀함수의 장단점

장점 

- 코드가 간결하고 이해하기가 쉽다. 

- 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다.

 

단점

- 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다.

- 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다.

- 반복문을 사용하는 것에 비해 실행 속도가 느릴 수 있다.

 

 

팩토리얼

- 팩토리얼 함수는 자연수 n에 대해 n! = n * (n-1) * (n-2) * ... * 2 * 1을 계산하는 함수입니다.

 

- 위의 코드에서 factorial(n)은 자신이 호출될 때마다 factorial(n-1)을 호출합니다. 이때, n == 1인 경우에는 재귀 호출을 멈추고 1을 반환합니다. 이를 통해, factorial(n) 함수는 n! 값을 계산할 수 있습니다.

 

피보나치수열

- 피보나치 수열은 이전 두항의 합이 다음 항이 되는 수열입니다. 위의 코드는 피보나치 수열을 재귀함수 구현한 코드로

n이 2이하 일경우 1을 반환해줍니다.

 

- 다만, 피보나치 수열을 재귀함수로 구현할경우 시간복잡도가 O(2^N)이 되므로 다른 알고리즘으로 구현하는것이 효율적입니다.

 

Stack overflow

- 재귀함수에서 함수 호출 스택의 제한된 크기를 초과하여 스택에 더이상 프레임을 추가할 수 없을 때 발생합니다. 

 

 

위의 코드는 인자로 받은 n부터 1까지 출력하는 함수입니다. 그러나, 만약 입력 값이 너무 큰 경우 함수 호출 스택의 크기가 한계치를 초과하여, 스택오버플로우가 발생할 수 있습니다. 따라서 재귀함수를 구현할 때는 호출 스택의 크기에 대해 고려하고, 필요하다면 반복문 등 다른 방법을 사용하여 구현해야 합니다.

 

꼬리재귀(tail call recursion)

- 재귀 함수의 주요 단점은 깊이가 깊어지면 스택 오버플로우(Stack Overflow)가 발생할 수 있다는 것입니다.

하지만 꼬리 재귀 함수(Tail Recursive Function)는 이러한 문제를 극복할 수 있습니다.

 

- 꼬리 재귀함수는 함수 호출의 결과로 반환되는 값에 함수 인자를 직접적으로 포함시키는 방식으로 구현됩니다. 이렇게 구현된 함수는 컴파일러가 최적화를 수행하여 스택 메모리를 추가로 사용하지 않고, 반복문과 같이 빠르게 실행될 수 있습니다.

 

 

위의 코드는 파이썬 코드로 반환부에 연산이 없도록 꼬리 재귀함수를 구현한 코드입니다. 다만, 파이썬은 꼬리 재귀함수를 최적화하지 않는 언어이므로, 파이썬에서는 꼬리 재귀를 사용해도 스택 오버플로우 문제를 완전히 해결할 수는 없습니다. 

 

 

Reference

- 재귀 함수 : https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60