재귀 (1) : Call me

오늘은 컴퓨터 과학에서의 재귀의 개념에 대해서 알아보도록 하겠습니다.

---

1. 재귀 ( Recursion )란?

재귀란 무엇일까요?
여기 너무나도 명확하게 답해줄 수 있는 예시가 있습니다.

function foo() {
  foo();
}

이와같이 재귀란 함수가 자기 자신을 재호출하는 로직을 뜻하는 용어입니다.

 

다른 예를 하나 더 볼까요?

function CountDown(number) {
	for(let i=number; 0 <= i; i--){
    	console.log(i);
    }
}

루프를 돌며 전달된 숫자만큼의 카운트 다운을 하는 함수입니다.

이것을 앞서 언급한 재귀로도 구현할 수 있습니다.

function CountDown(number) {
	console.log(number);
    	CountDown(number-1);
}

이처럼 위와 같은 방식으로  (일반적으로) Loop 문은 재귀로 대체할 수 있습니다

하지만 위의 두 재귀의 예시들은 치명적 문제를 가지고 있습니다.

---

 

2. 기저 조건

바로 함수가 종료되지 않고 무한히 호출된다는 것입니다.

그래서 영원히 지속 되지 않고 원하는 상황에서 반환하게 할 수 있는 로직이 요구되는데 이를 기저 조건 ( Base case )라고 합니다

위의 CountDown 예시를 기저 조건을 추가해 정상적인 동작을 하도록 수정해 보겠습니다.

function CountDown(number) {
	console.log(number);
    	// 기저 조건
	if(number === 0) {	
        return;
        }else {
            CountDown(number-1)
        }
}

 기저 조건이 추가되면서 0 이 되면 모든 재귀 함수가 반환됩니다.

이처럼 기저 조건이 핵심인 만큼 재귀 함수를 읽을 때는 기저조건을 우선 찾고 해당 부분부터 분석해 나가는 것이 좋은 방법입니다.

 

---

 

3. 컴퓨터의 재귀 처리 방법

$ Factorial $함수를 정의하였다고 가정하고 $ Factorial(5) $가 호출되었을 때에 대해서 얘기해 보겠습니다.

 

function factorial(n) {
	// 기저조건
    if (n === 1) {
        return 1;
    }
    return n * factorial(n - 1)
}

$ Factorial(5) $가 호출되었을 때 => 5는 기저 조건이 아니기에 $ Factorial(4) $를 호출합니다.
$ Factorial(4) $가 호출 되었을 때 => 4는 기저 조건이 아니기에 $ Factorial(3) $를 호출합니다.
...
$ Factorial(1) $가 호출 되었을 때 => 1은 기저 조건이기에 반환합니다.

 

factorial(5) 진행 중 factorial(4)를 호출하였을 때 factorial(5) 함수의 진행은 아직 종료되지 않았습니다.

실행이 종료되기 전에 자기 자신을 재호출 한 것인데요. 그렇다면 진행중인 정보는 어디에 기록할까요?

바로 호출 스택 ( Call stack )이라는 이름으로 스택 자료구조가 사용됩니다.

함수가 호출을 거듭하던 중 기저 조건을 만났을 때 다시 마지막 호출 함수부터 첫 호출 함수까지 역순으로 반환하는 구조이기에 ( LIFO ) 적절한 자료 구조인 스택이 사용되었습니다.

 

 

---

마치며

이번 포스팅에서는 재귀 호출에 대해 살펴보았습니다.
개발에 있어 전반적으로 굉장히 유용하게 쓰일 수 있는 알고리즘 도구입니다.
특히 알 수 없는 깊이의 단계까지 깊게 들어가야 하는 경우에 많이 쓰입니다.
사실 개인적으로는 코드를 읽는 데에 어려움이 있어 선호하지는 않습니다.
다만 사용할 때에 주어진 메모리의 크기를 넘기지 않도록 주의합시다.
지나치게 많은 재귀 호출은 제한된 메모리 크기를 넘어 stack overflow 가 발생할 수 있습니다.

 

관련글

재귀 (2) : 미래의 나야, 부탁해~

 

재귀 (3) : 효율적인 재귀 사용