재귀함수

함수에서 자신을 호출하는 함수를 재귀함수라고 한다

장점

• 여러개의 반복문을 사용할때 재귀 함수를 사용하면 코드가 간결해지고 수정이 편하다
• 변수를 여러개 쓸 필요가 없다.

단점

• 코드의 흐름이 직관적으로 파악하기 어렵다.
• 반복해서 자신을 호출하기 때문에 이때 사용하는 매개변수, 지역변수,리턴 값등등 지속적으로 Stack에 저장되기때문에 메모리를 많이 사용한다.
• 함수 호출하고 종료할때 복귀할때 context switching(컨텍스트 스위칭)비용이 발생해 속도가 좀 느리다.

조건

• 재귀 함수 호출이 종료되는 시점이 있어야 무한대로 안한다.
• 작은단위로 계속 쪼갤수 있어야한다.

예제

팩토리얼(factorial)

public class test {
    public static void main(String[] args) {
        System.out.println(Factorial(5));
    }
    public static int Factorial(int num){
        if (num <= 0) return 1;
        return num * Factorial(num - 1);
    }
}

1부터 num까지 곱 계산하는 함수입니다.

1~N까지 합

public class test {
    public static void main(String[] args) {
        System.out.println(sumTo(20));
    }
    public static int sumTo(int num){
        if (num == 0) {
            return 0;
        }

        return num + sumTo(num-1);
    }
}

1~N까지 합계를 출력합니다.
반복문을 안쓰고 재귀함수를 이용했습니다.

피보나치

public class test {
    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
    public static int fibonacci(int num){

        if(num==0){return 0;}
        if(num==1){return 1;}

        return fibonacci(num-1)+fibonacci(num-2);
    }
}

피보나치 수열은 0 1 1 2 3 5 8 13