재귀 함수 : 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수

재귀함수로 팩토리얼 구현

def factorial (n:int)->int:
	if n>o:
    	return n*factorial(n-1)
    else :
    	return 1
        
n= int(input("출력할 팩토리얼값을 입력하라:")
print(f'{n}의 팩토리얼은 {factorial(n)} 입니다.')

n=3일 경우 3*2*1*1 로 재귀적으로 들어갑니다.

재귀(Recursive) vs 반복(Iteration)

반복과 재귀의 가장 큰 차이는, 재귀는 스스로를 호출한다는 점에 있다.

재귀함수와 반복의 시간복잡도

재귀
재귀의 시간 복잡도는 이전 호출의 입장에서 n번째 재귀 호출의 값을 알아내면 알 수 있다.
그러므로 종결 조건(Terminating case, Base case) 입장에서 목적 조건(Destination case)을 찾고, 종결 조건 입장에서 해결하는 것이 재귀식의 시간 복잡도를 계산하는 것의 아이디어가 된다.
재귀는 시간 복잡도를 계산하는 것이 어렵다.
반복
반복의 시간 복잡도는 비교적 간단히 루프 내의 반복되는 사이클의 수를 알아내면 알 수 있다.

언제 사용하는가?

두 방식은 시간 복잡도와 코드의 양에서 상호교환적(Trade-off)인 측면을 보인다.
시간 복잡도의 측면에서 보면, 재귀 호출의 수는 클 것이고 반복을 쓰는 것이 좋을 수 있다. 하지만 코드의 길이를 중점으로 한다면, 재귀가 나을 수 있다.

재귀
재귀는 같은 함수를 호출하고 호출한다. 때문에 코드의 길이는 짧다. 그러나 분석을 해보면, 호출이 상당히 많아지면 시간 복잡도가 지수 단위(Exponential)로 증가할 수 있다.
그러므로, 재귀의 사용은 짧은 코드라는 점에서 이점이지만, 반복보다 높은 시간 복잡도를 가진다.
반복
코드 블록의 반복이다. 이것은 코드가 길어지게 되지만, 일반적으로 재귀보다 낮은 시간 복잡도를 가진다.

오버헤드

재귀는 반복과 비교하여 큰 오버헤드를 가진다.

재귀
재귀는 반복되는 함수 호출에서 오버헤드를 가진다.
이는 동일한 함수를 반복 호출하는 것이 코드의 시간 복잡도가 증가하는 점을 말한다.
반복
반복은 그러한 오버헤드를 가지지 않는다.

무한 반복

무한 반복이 발생하는 경우 재귀는 CPU 크래시를 초래할 수 있지만, 반복은 메모리가 부족할 때가 되면 멈춘다.

재귀
종결 조건을 명시할 때 실수를 하면, 무한 재귀 호출이 생길 수 있다.
예를들어 조건이 false가 되지 않아 계속 함수를 호출하게 되면 CPU 크래시가 발생할 수 있다.
반복
반복자 실수(반복자 배정이나 증가) 혹은 종료 조건(terminating condition)을 실수하면 무한 루프가 발생한다.
시스템 에러가 발생할 수도, 발생하지 않을 수도 있지만 어쨋든 프로그램이 확실하게 중지될 것이다.

위의 단점에도 불구하고 재귀를 쓰는 이유?

1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울때 가독성이 좋다.

2. 변수 사용이 줄어든다.

꼬리재귀(

재귀 호출 이후 추가적인 연산을 요구하지 않도록 구현하는 것

이 방식을 사용하면 이전 함수의 상태를 유지하지도 않고 추가 연산을 하지 않아 스택이 넘쳐나는 문제를 해결 할 수 있다.

꼬리재귀를 구현하기 위한 조건

재귀 함수를 꼬리 재귀 방식으로 구현할 것
컴파일러가 꼬리 재귀 최적화를 지원할 것
C++, C#, Kotlin, Swift은 꼬리 재귀 최적화를 지원하며,
JavaScript는 ES6 스펙에서 지원한다고 한다.
Scala는 JVM 위에서 동작하는데, 꼬리 재귀 최적화를 지원한다고 한다.
하지만 Java는 꼬리 재귀 최적화를 직접적으로 지원하지 않는다.

참고 블로그

저작자표시 (새창열림)

윤SW

재귀 알고리즘