티스토리 뷰

오랜만에 재귀 문제를 풀다보니 헷갈려져서 정리한번 해보겠음.

재귀 중에 가장 쉬운 팩토리얼부터..



1. 재귀함수란?


함수 내에서 자기 자신을(함수)를 계속적으로 콜 하면서 풀어가는 방식이다.

스택(Stack)이라고 생각할 수 있다.

함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 됨.

중요한건 

처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다



2. 팩토리얼이란?


3! = 3*2*1 = 6

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

5! = 5*4*3*2*1 = 120



3. 재귀 예제


문제 : 특정 숫자의 팩토리얼 구하기 


간단하게 소스 투척


public class Factorial {

public static void main(String[] args) {

int input = 4; // 4!

System.out.println(fact(input));

}


public static int fact(int n) {

if (n <= 1)

return n;

else 

return fact(n-1) * n;

}

}



>> 결과


24 



4. 원리


1) 처음 fact 메소드가 불린 것은 main 함수에서이다.

fact(4) 가 실행될 것이다.


2) fact(4)

n은 현재 4이다.

n은 1보다 크므로 else를 타고,

fact(3)이 호출된다.


3) 여기서 처음 호출된 fact(4)는 종료되지 않고 Stack에 쌓인상태로,

fact(4)가 호출한 fact(3)이 실행된다.


Stack

 fact(4)


4) fact(3)

n은 현재 3이다.

n은 1보다 크므로 else를 타고,

fact(2)이 호출된다. 


5) 여기서 두번째로 호출된 fact(3)은 종료되지 않은 상태로 Stack에 쌓이고,

fact(3)이 호출한 fact(2)이 실행된다.


Stack

fact(3) 

fact(4)


6) fact(2)

n은 현재 2이다.

n은 1보다 크므로 else를 타고,

fact(1)이 호출된다.


7) 세번째로 호출된 fact(2)는 종료되지 않은 상태로 Stack에 쌓이고

fact(2)가 호출한 fact(1)이 실행된다.


Stack

fact(2) 

fact(3)

fact(4)


8) fact(1)

n은 현재 1이다.

n이 1과 같으므로 if문을 타고, n 즉, 1을 return 한다.


9) fact(1)이 종료되면서, Stack의 가장 위에 있는 fact(2)가 실행된다.

8번에서 리턴 받은 값과 n을 곱하며 return 하고 fact(2)가 종료될 것이다.


fact(2) 에서는 n이 2이다.

8번에서 fact(1)은 1을 리턴했었다.


 fact(2-1) * n  즉,  1 * 2


그래서 fact(2)에서는 1*2 한 값을 return 한다.


Stack은 이제 아래와 같은 상태가 된다.

fact(3) 

fact(4)


10) 스택에 있던 fact(3)이 실행된다.

9번에서 리턴 받은 1*2 = 2 와 n을 곱하며 리턴하고 종료한다.


 fact(3-1) * n  즉,  2 * 3


fact(3)은 1*2*3 한 값 6을 리턴한다.


11) 마지막으로, 처음 불리워졌었던 fact(4)가 리턴할 차례가 왔다.

10번에서 리턴받은 6과 n을 곱하고 리턴하고 종료될 것이다.


 fact(4-1) * n  즉,  6 * 4 = 24



이렇게 4! 을 구했고, 리턴 받은 값은 main 함수에서 출력된다.


결론적으로 따져보면

1*2*3*4 를 하게 된 것이다.



저작자 표시 비영리
신고
댓글
  • 프로필사진 지나가는 나그네 정말 감사합니다.

    한큐에 이해가 됐습니다.
    2017.03.28 01:35 신고
  • 프로필사진 느루 자바언어를 아예 몰라서 감으로 코드를 읽어야했네요.
    멍청한 중생을 위해 글을 써주셔서 감사합니다.
    근데 이해가 안가는게 있어 답글을 답니다.
    아... 질문에 답을 해주셨으면 감사하겠네요.

    함수가 왜 스택에 쌓이는지 이해가 안갑니다.
    어떤 경우에 스택에 함수가 쌓이고 어떤 경우에 날아가는지 알고싶습니다.
    그리고 스택에 쌓이는 함수가 어떻게 실행되는건지를 모르겠습니다.
    2017.08.08 06:22 신고
  • 프로필사진 신매력 C나 자바언어같은 경우 함수를 스택 메모리에 쌓고 맨위에(가장 최근에 쌓인) 것을 pop하면서 수행을 합니다.
    함수를 스택에 쌓는 이유는 변수를 메모리에 적재 하듯이 함수도 메모리에 올려야 합니다.
    함수들의 수행 순서가 함수가 함수를 호출하고, 완료 후 이전 함수로 다시 돌아가고..를 반복하기 때문에, 그에 적절한 스택구조를 사용하는 것입니다.
    2017.08.18 21:03 신고
댓글쓰기 폼