재귀함수(Recursive Function) 란?

특정 조건(= 끝나는 조건)이 될 때까지 자기자신을 계속 호출하는 함수이다.
함수 안에 끝나는 조건이 있고, return에서 자기 자신을 호출한다.
재귀함수는 같은 규칙을 가지는 함수를 반복해서 사용할 경우 적용할 수 있다.

예를들어 1부터 4까지의 합을 구할 때

1~1의 합 sum(1) = 1
1~2의 합 sum(2) = 1 + 2 = sum(1) + 2
1~3의 합 sum(3) = 1 + 2 + 3 = sum(2) + 3
1~4의 합 sum(4) = 1 + 2 + 3 + 4 = sum(3) + 4

sum(n) = sum(n-1) + n

위의 식을 프로그램으로 적용하면

public static int sum(int n) {
    // 끝나는 조건  : n=1 이면 반복수행 중단
    if(n == 1)
        return 1;

    // 일반화된 규칙, 자기자신을 계속 호출
    return sum(n-1) + n;
}

팩토리얼 (factorial )

1부터 양의정수 n까지의 곱으로 이루어진 팩토리얼도 위와 같은 방법으로 구현이 가능하다.
예를들어 4!(4x3x2x1)를 구할 때

1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
4! = 4 * 3! = 24

n! = n * (n-1)!

위의 식을 프로그램으로 적용하면

private static int factorial(int n) {

    // 끝나는 조건
    if (n == 1)
        return 1;

    // 일반화된 규칙, 자기자신을 계속 호출
    return n * factorial(n-1);
}

피보나치 수열 (Fibonacci Sequence)

앞의 두 수의 합이 바로 뒤의 수가 되는 배열

f(1) = 1
f(2) = f(1) + f(0) = 1
f(3) = f(2) + f(1) = 1 + 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3

f(n) = f(n-1) + f(n-2)

public static int fibonacci(int n) {

    // 끝나는 조건
    if(n <= 2) {
        return 1;
    }

    // 일반화된 규칙, 자기자신을 계속 호출
    return fibonacci(n-1) + fibonacci(n-2);
}

이 외에 재귀함수를 이용한 예제는 아래 GitHub에서 확인할 수 있다. GitHubs 소스 다운로드

소스보기

소스로딩 실패

실행결과