[section 2] 알고리즘(1) - 재귀

재귀 함수

함수 내에서 자기 자신을 호출하는 함수

장점

1. 불필요한 반복문을 줄임으로써 코드가 간결해짐
2. 수정이 쉬움
3. 변수를 여러개 사용하지 않아도 됨

단점

1. 코드의 흐름을 직관적으로 파악하기 힘듦
2. 메소드 호출의 반복으로 지역변수, 매개변수, 반환값 등 저장해야 할 데이터들이 많아지고, 반복문에 비해 메모리를 많이 사용하게 됨
3. 복귀를 위한 컨텍스트 스위칭 비용 발생
   컨텍스트 스위칭 context switching
   : 여러개의 프로세스가 실행되고 있을 때 기존에 실행되던 프로세스를 중단하고 다른 프로세스를 실행하는 것

조건

1. 문제의 크기를 작은 단위로 쪼갤 수 있어야 함
2. 재귀가 종료되는 시점, 탈출 조건이 있어야 함

예시 코드

// 1부터 n까지 더하는 재귀함수
public int recursion(int n) {
	// 탈출 조건
	if (n == 1) return 1;
    // 재귀
    return n + recursion(n - 1);
}