재귀 함수

재귀 함수

>의미

: 자기 자신을 호출하는 함수

>사용

: 문제를 쪼개면, 같은 문제지만 작은 크기의 문제로 될 때 주로 사용

>장점

: 가독성이 좋아짐(단순한 코드로 보이게 할 수 있음)

: 변수의 갯수를 줄일 수 있음

>단점

: 코드는 짧지만 표현이 직관적이지 못해 오히려 보기 힘들 가능성이 높음.

: 메모리 사용량이 굉장히 높음(Stack Overflow)

>특징

: 함수의 입력값(매개변수), 리턴값, 리턴 후 돌아갈 위치 등이 Stack 메모리에 저장됨.

: 단점 가득한, 굳이 안써도 되는 함수

: 문제 풀이에 사용되는 경우가 제일 일반적임.

꼬리 재귀

>의미

: 재귀를 그나마 안전하게 사용할 수 있는 방법 중 하나

: 재귀 호출이 끝나면 다른 작업 없이 결과만 반환하도록 하는 방법

>특징

: 함수의 몸체 마지막 부분(꼬리)에서 재귀 함수 호출

: 함수내에 연산을 하는 부분을 따로 작성한다

: 연산 부분이 따로 존재하기 때문에 매개변수와 인자를 2개 이상을 사용하는 듯 하다.

: 추가로 연산할 필요가 없기 때문에 자리를 기억하는 것에 메모리가 사용되지 않음.

 

일반 재귀와 꼬리 재귀의 대표 예시(팩토리얼)

//일반 재귀 예시
//: 재귀 종료 시, 남아있는 n들과 연산이 이루어진다.
int factorial(int n) {
        if (n == 1) return 1;
        return n * factorial(n-1);
}
/*
System.out.println(factorial(5));
120
*/

//꼬리 재귀 예시
//: 재귀 중 연산 과정은 재귀 호출 문장과 다른 문장에서 이루어진다.
int factorialTail(int n,int acc){
        if(n == 1) return acc;
        return factorialTail(n - 1, n * acc);
}
/*
System.out.println(factorialTail(5, 1));
120
*/