재귀함수

함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식
특정한 트리거가 있지 않는 이상 지속적으로 자기 자신을 호출해 작업을 진행해 반복문을 구현할 때 사용한다.

대표적으로 "펙토리얼 함수", "하노이의 탑" 등을 구현할 때 사용된다.

반복문(for, while)에 들어가야할 변수들을 다수 생성하지 않고, 동일한 매개변수를 통해 반복 작업을 하는 것이기 때문에 변수의 수를 줄일 수 있다.
함수를 호출하게 되면 해당 함수에 대한 지역변수, 매개변수, 반환값을 모두 stack에 저장해야 하는데, 재귀함수에서 자기 자신을 많이 호출하게 되면 그만큼 메모리를 사용하게 되기 때문에 속도 저하가 될 수 있습니다. 또한 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 됩니다.

▷ 위 단점을 없에기 위해서 꼬리 재귀를 사용하는 경우가 많아졌다.

꼬리 재귀(tail call recursion) :

자기 자신을 기다리며 생기는 메모리 낭비를 최소화 시키기 위해 재귀 호출이 끝나는 시점에서 바로 결과만 반환하도록 함수를 구성하는 것

반환 시점에 함수의 상태유지 및 추가 연산을 하지 않기에 메모리 사용률을 줄일 수 있다.

---

소스

작성 언어 java

// 펙토리얼 함수
public static int fac(int num){
    if(num == 1){
        return 1;
    }else{
        return num * fac(num - 1);
    }
}

// 펙토리얼 함수(꼬리 재귀)
public static int facTail(int num, int result){
    if(num == 1){
        return 1;
    }else{
        return fac(num - 1, result * num);
    }
}

참고

https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60
https://wayhome25.github.io/cs/2017/04/15/cs-16-1-recursion/