재귀함수란?
함수 내에서 자기 자신(함수)을 계속적으로 호출 하면서 풀어가는 방식.
함수가 호출 되면서 최근에 자신을 불렀던 기존 함수가 스택에 차곡차곡 쌓이게 된다.
처음 호출된 함수(스택 맨 밑에 있는 메소드)에서 return 되는 값이 최종 return 값이 된다.
팩토리얼이란?
3! = 3*2*1 = 6
4! = 4*3*2*1 = 24
5! = 5*4*3*2*1 = 120
문제
재귀를 이용한 특정 숫자의 팩토리얼 연산
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
설명
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)가 호출된다.
Stack
fact(3)
fact(4)
5) 이 때 호출된 fact(3) 또한 종료되지 않은 상태로 Stack에 쌓이고, fact(3)이 호출한 fact(2)이 실행된다.
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*2 한 값을 return 한다.
fact(2-1) x n → 1 x 2
Stack은 이제 아래와 같은 상태가 된다.
Stack
fact(3)
fact(4)
이후 같은 과정을 반복하면 1*2*3*4를 연산해 24의 결과값이 나오게 된다.
