재귀 recursive function

재귀 함수란?

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

• 반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현하는 것이 가능하며 그 반대도 가능
• 코드가 간결하고 이해하기 쉽다. 특정 유형의 문제(트리, 그래프 탐색 등)에 매우 적합함
• 반복적인 스택의 사용으로 인해 메모리 및 속도에서 성능 저하가 발생할 수 있음

 

예시

 def factorial(n):
 	if n<=1 :
    	return 1 # 종료 조건 필수
    else :
    	return n * factorial(n-1)

즉, 재귀 문제를 풀 때는 항상 base case와 recursive case로 경우를 나누어 주어야 함

base case : 더 이상 자기 자신을 호출하지 않고, 직접 결과를 반환하는 조건

 

꼬리 재귀 (taili recursion)

• 함수 호출의 결과로 반환되는 값에 함수 인자를 직접적으로 포함시키는 방식으로 구현
• 재귀로 구현하고 싶은데, 재귀가 가지는 오버헤드를 피하고 싶다면 사용!
• 재귀 호출 후 추가적인 연산이 필요하지 않다면 일반 함수를 호출하는 것처럼 시스템 콜 스택에 이것저것 저장하지 않고 선형적으로 구현할 수 있음
• 이렇게 구현된 함수는 컴파일러가 최적화를 수행하여 스택 메모리를 추가로 사용하지 않고, 반복문과 같이 빠르게 실행될 수 있음 (only 컴파일 언어)
• 그러나 python은 인터프리터 언어라 자동적으로 최적화를 수행하지 않음.
• tail recursion elimination : 꼬리 재귀 조건을 만족한다면 실제로 함수를 호출하지 않고 반복문을 활용하도록 구현한 방식

int factorialTail(int n, int acc){
	if(n == 1) return acc;
    return factorialTail(n - 1, acc * n);
}
int factorial(int n){
    return factorialTail(n, 1);
}