재귀함수의 원리 및 동작

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

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

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 를 하게 된 것이다.