재귀함수와 꼬리재귀

재귀함수

• 자기 자신을 호출하는 함수
• 종료조건이 필수적으로 필요하다

<팩토리얼을 재귀함수와 for문으로 작성한 코드>

import java.util.Scanner;

public class FactorialCalculator {
    //재귀함수
    static int factorial(int num) {
        if (num > 0){
            return factorial(num-1) * num;
        } else{
            return 1; //0!은 1이다.
        }
    }

    //for문으로 구현한 함수
    static int factorialForGrammar(int num) {
        int result = 1;
        if (num > 0){
            for(int i = num; i < 0; i--){
                result *= num;
            }
        }else {
            result = 1;
        }
        return result;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num = 0;

        do {
            System.out.print("펙토리얼을 구하고자하는 양의 정수를 입력하세요: ");
            num = sc.nextInt();
        }while(num < 0);

        System.out.println(factorial(num));
        System.out.println(factorialForGrammar(num));
    }
}

꼬리재귀

위의 팩토리얼 재귀함수 코드를 보면 return뒤에 아래와 같은 형태로 되어있는 것을 볼 수 있다.

factorial(num-1) * num;

 

꼬리재귀는 재귀함수에 다른 연산을 하는 것이 아닌 모조건 return뒤에 재귀함수 본인만 오는 것을 말한다.

 

<팩토리얼을 꼬리재귀로 작성한 코드>

import java.util.Scanner;

class TailRecursiveFactorial {
    // 꼬리 재귀를 사용한 팩토리얼 계산 메서드
    static int factorial(int n, int accumulator) {
        if (n == 1) return accumulator;
        return factorial(n - 1, n * accumulator); // 꼬리 재귀 호출
    }

    // 사용자가 입력한 숫자에 대해 팩토리얼을 계산
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.print("팩토리얼을 계산할 정수를 입력하세요: ");
        int x = stdIn.nextInt();
// 초기 누적 변수 값으로 1을 사용
        int result = factorial(x, 1);
        System.out.println(x + "의 팩토리얼은 " + result + "입니다.");
    }
}