1.
재귀 용법
•
함수 안에서 동일한 함수를 호출하는 형태
2.
재귀 용법 이해
•
예제를 풀어보며, 재귀 용법을 이해해보기
예제
•
팩토리얼을 구하는 알고리즘을 Recursive Call을 활용해서 알고리즘 작성하기
예제 - 분석하기
•
간단한 경우부터 생각해보기
◦
2! = 1 x 2
◦
3! = 1 x 2 x 3
◦
4! = 1 x 2 x 3 x 4
•
규칙 n! = n x (n-1)!
1. 함수를 하나 만든다.
2.
함수(n)은 n > 1 이면 return n x 함수(n-1)
3.
함수(n)은 n = 1 이면 return n
예제 - 코드 레벨로 적어보기
public class RecursiveCall {
public int factorialFunc(int n)
{
if(n>1) {
ㅟ
Java
복사
예제 - 시간 복잡도와 공간 복잡도
•
factorial(n) 은 n-1 번의 factorial() 함수를 호출해서, 곱셈을 함
◦
일종의 n-1 번 반복문을 호출한 것과 동일
◦
factorial() 함수를 호출할 때마다, 지역변수 n이 생성됨
•
시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)
3.
재귀 호출의 일반적인 형태
간단한 메서드 레벨로 보기로 함
// 일반적인 형태1function(입력) {
if (입력> 일정값) {// 입력이 일정 값 이상이면return function(입력- 1);// 입력보다 작은 값
}else {
return 특정값;// 재귀 호출 종료
}
}
Plain Text
복사
// 일반적인 형태2function(입력) {
if (입력<= 일정값) {// 입력이 일정 값보다 작으면return 특정값// 재귀 호출 종료
}
return function(입력- 1);
}
Plain Text
복사
재귀 호출은 스택의 전형적인 예
•
함수는 내부적으로 스택처럼 관리된다.
