재귀함수

재귀함수

메소드 안에서 자기 자신을 다시 호출하는 형태의 메소드

재귀가 끝나면 남은 코드는 역순으로 실행된다.

문제

자기 자신을 계속해서 호출하여 스택에 push하기 때문에 메모리 문제가 생길 수 있다. 따라서 적절한 종료조건을 명시해야한다.

팩토리얼 계산

1부터 매개변수로 받아온 값까지의 곱을 구한다.

받아온 매개변수를 1씩 감소시켜가며 현재 매개변수값과 메소드 리턴값을 곱해준다.

매개변수가 1이되면 최종리턴된다.

    public Integer calc(Integer num){
        if(num == 0){
            return 1;
        }else {
            return num * calc(num-1);
        }
    }

하노이 타워

크기가 다른 원반을 크기 순서에 맞게 특정 고리로 이동시키는

하노이 타워 규칙

원반 위에는 자신보다 크기가 작은 원반만 올 수 있다.

한 번에 원반은 한 개씩만 옮길 수 있다.

구현

public class Hanoi {
    //하노이 타워
    //기둥 번호는 1 ~ 3번
    //원반번호는 가장 작은원반부터 1,2,3
    // 이동(원반 번호 / from / to)를 전달받는다
        // 원반 번호가 1보다 크면 원반번호-1을 from에서 from과 to가 아닌 곳으로 이동
        // 원반 번호를 from에서 to로 옮겼다고 출력
        // 원반 번호가 1보다 크면 원반 번호 -1을 from과 to가 아닌 곳에서 to로 이동
    public void move(Integer ring, Integer from, Integer to){
        if (ring > 1){
            move(ring-1, from, 6-from-to);
        }
        System.out.printf("%d에서 %d로 옮김\n", from,to);
        if (ring > 1){
            move(ring-1, 6-from-to, to);
        }
    }
}