재귀호출이란?

- 메소드 내에서 자기자신을 반복적으로 호출하는 것
- 재귀호출은 반복문으로 바꿀 수 있으며 반복문보다는 성능이 나쁨
- 이해하기 쉽고 간결한 코드를 작성할 수 있음

재귀호출의 예

- 팩토리얼, 제곱, 트리운행, 폴더목록표시 등

재귀 호출을 사용하여 1부터 n까지의 합을 구하는 recursiveSum() 메소드를 만들어 보자

우선 1부터 4까지의 합을 구하는 알고리즘을 생각해 본다.

의사 코드

시작
    1. n이 1이 아니면, n과 1부터 (n-1)까지의 합을 더한 값을 반환함.
    2. n이 1이면, 그냥 1을 반환함.
끝

의사 코드(pseudo code)란 특정 프로그래밍 언어의 문법에 맞춰 작성된 것이 아닌, 일반적인 언어로 알고리즘을 표현한 코드를 의미

예제

int recursiveSum(int n) {
    if (n == 1) {                 // n이 1이면, 그냥 1을 반환함.
        return 1;
    }
    return n + recursiveSum(n-1); // n이 1이 아니면, n을 1부터 (n-1)까지의 합과 더한 값을 반환함.
}

실행결과

55

위의 예제에서 if 문이 존재하지 않으면, 이 프로그램은 실행 직후 스택 오버플로우(stack overflow)에 의해 종료된다.

따라서 if 문처럼 재귀 호출을 중단하기 위한 조건문을 반드시 포함해야 한다.

스택 오버플로우(stack overflow)는 메모리 구조 중 스택(stack) 영역에서 해당 프로그램이 사용할 수 있는 메모리 공간 이상을 사용하려고 할 때 발생

실습 - ch06 / S07.java

주석으로 설명..

package ch06;

class temp{
    // 자기 자신을 호출하는 함수
    // 재귀함수
    public static int myFunction(int b){
        int a = 1;
        if (a + b > 0) {
            System.out.println("10보다 작습니다.");
            return myFunction(a + b);
        } else {
            return a + b;
        }

    }

}

public class S07 {
    public static void main(String[] args) {
        // temp.myFunction(0);

        // 대부분의 재귀 함수는 반복문으로 바뀔 수 있다
        // 특별한 경우가 아니면 재귀함수는 자제한다.
        while(true){
            System.out.println("10보다 작습니다.");
        }
    }
}