[method] Java - Recursion (재귀)

1. Java Recursion (재귀)
2. 재귀 예제
3. 재귀 무한 반복을 막는 정지 조건

Java Recursion (재귀)

※ 메서드는 함수의 일종.

 

1.

재귀 : 함수 안에서 함수 자신 호출.

 

2.

가장 안쪽 함수의 반환값 이용해,

밖으로 거슬러 나오며 결과 반환.

 

※ 사용 시, 주의 !! 

더 간결할 수도, 때론 훨씬 더 복잡할 수도 있음.

또한, 정지조건 없을 시, 무한 반복 되니 주의 !!

 

재귀 예제

※ 1부터 4까지 합.

 

public class Hz {

  public static void main(String[] args) {

    int result = sum(4);

    System.out.println(result);

  }

  public static int sum(int k) {

    if (k > 0) {

      return k + sum(k - 1);

    } else {

      return 0;

    }

  }

}

 

결과값: 10

---

PS. 작동 원리

 

sum(4) = 4 + sum(3)

sum(3) = 3 + sum(2)

sum(2) = 2 + sum(1)

sum(1) = 1 + 0 = 1

sum(2) = 2 + 1 = 3

sum(3) = 3 + 3 = 6

sum(4) = 4  + 6 = 10

 

재귀 무한 반복을 막는 정지 조건

 

모든 재귀함수는 정지 조건 (= 재귀 무한 반복 막는 조건)갖어야 함.

위 예제 경우, k=0 조건이 반복 정지 조건.

아래 예제는, end > start 조건이 반복 정지 조건.

 

---

[예제] 1부터 4까지의 합.

public class Hz {

  public static void main(String[] args) {

    int result = sum(1, 4);

    System.out.println(result);

  }

  public static int sum(int start, int end) {

    if (end > start) {

      return end + sum(start, end - 1);

    } else {

      return end;

    }

  }

}

 

결과값: 10

---

PS. 작동원리.

 

sum(1, 4) = 4 + sum(1, 3)

sum(1, 3) = 3 + sum(1, 2)

sum(1, 2) = 2 + sum(1, 1)

sum(1, 1) = 1

sum(1, 2) = 2 + 1 = 3

sum(1, 3) = 3 + 3 = 6

sum(1, 4) = 4 + 6 = 10