재귀 알고리즘

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다.

 

function ex() {
	ex();
}

 

재귀에서 메서드가 반복되지 않는 경우를 기저 조건(중단 조건) 이라 부른다.

 

 

재귀를 다루는 컴퓨팅 사고

function factorial(number) {
	if (number === 1) {
    	return 1;
    } else {
    	return number * factorial(number - 1);
    }
}

factorial(3);

위의 코드를 실행시키면 일어나는 컴퓨팅 사고

1. factorial(3)이 먼저 호출된다.

2. factorial(2)가 두 번째로 호출된다.

3. factorial(1)이 세 번째로 호출된다.

4. factorial(1)이 먼저 완료된다.

5. factorial(2)가 factorial(1)의 결과를 토대로 완료된다.

6. 끝으로 factorial(3)이 factorial(2)의 결과를 토대로 완료된다.

 

무한 재귀가 있을 때 프로그램은 컴퓨터 메모리에 더 이상 공간이 없을 때까지 같은 메서드를 호출 스택에 푸시한다. 이로 인해 발생하는 오류는 스택 오버플로라고 부른다.