재귀함수

1. 재귀함수란

• 자기 자신을 호출하는 메서드로 특정 조건이 없다면 무한 반복함
  • 특정 조건에 해당하면 더 이상 호출하지 않도록 해야 함
  • 고급 정렬 알고리즘에서는 재귀용법을 많이 사용함
•  재귀함수는 전형적인 스택

이미지 출처 :  https://twitter.com/sunnypaxos/status/1359263593234104320?lang=zh-Hant

예) Factorial 구현

public class Factorial{
	public int factorialFunc(int n){

		if(n > 1){
			return n * this.factorialFunc(n - 1);
		} else{
			return 1;
		}

	}
}

2. 재귀함수의 형태 2가지

function(입력) {
	if(입력 > 일정값){ // 입력값이 특정 값보다 크명
		return function(입력 - 1); // 재귀 함수 호출
	}else{
		return 특정 값; // 재귀함수 호출 종료
	}
}

function(입력) {
	if(입력 <= 일정값){ // 입력값이 특정 값보다 작으면
		return 특정 값; // 재귀 함수 호출 종료
	}
	return function (입력 - 1); // 클 경우는 계속 재귀함수 호출
}

3. 시간 복잡도(O(n))

• n - 1번의 반복문을 호출 → O(n - 1) → O(n)

4. 공간 복잡도

• 호출할 때마다 인자를 위한 공간이 필요함 → n개의 공간이 필요하기 때문에 O(n)