재귀 함수 (recursive function) 의 동작

1. 재귀 함수란?

 

코드 내에서 본인을 호출하는 함수를 재귀함수라고 한다.

 

 

 

하지만 단순히 아래와 같이 자기 자신을 호출만 한다면 함수는 위 송강호씨처럼 영원히 자기 자신을 호출하기를 반복하게 될 것이다.

function recursive() {
  recursive();
}

recursive();

 

 

이를 방지하기 위해서 재귀함수는 코드 내에 탈출 조건을 포함하고 있어야 하고, 본인을 호출할 때마다 입력 파라미터가 탈출 조건에 수렴하는 양상으로 변화해야 한다.

function recursive(n) {
  if(n < 0){           //탈출 조건
    return;
  }
  recursive(n - 1);    //변화하는 파라미터, 0으로 수렴
}

recursive(5);

 

 

2. 반복문 vs 재귀 함수

대부분의 재귀 함수 동작은 변수값을 변화시켜가는 반복문으로 똑같이 구현할 수 있다. 

 

- 메모리

재귀함수가 본인이 본인을 호출한다고 해서 메모리 상에서도 본인이 차지했던 콜 스택 메모리를 재사용하는 것은 아니기 때문에 매 호출마다 콜 스택 메모리를 잡아먹게 된다. 

 

- 속도

각 함수 호출은 호출 스택에 추가되며, 이 과정에는 함수의 매개변수, 반환 주소, 그리고 로컬 변수 등을 저장하기 위한 시간이 소요되기 때문에 같은 목적으로 동작하더라도 반복문에 비해 재귀 함수는 속도가 느릴 수 밖에 없다.

 

그럼에도 불구하고 재귀 함수가 존재하는 이유는 재귀적 접근과 재귀 함수로 구현함으로써 반복문에 비해 훨씬 이해하기 쉽고 간결해지는 상황들이 존재하기 때문이다.

 

 

3. 재귀 함수의 동작 원리

 

재귀 함수를 이해하기 위해서는 당연히 함수의 동작에 대한 이해가 선행되어야 한다.

 

먼저 함수에 대한 정의와 정의된 함수를 호출하는 코드가 있을 것이다.

 

함수를 호출하면 정의된 함수 내 로직이 실행된 후 값을 반환하게 되고, 반환된 값은 함수를 호출했던 라인으로 간다는 것이 핵심이다.

function recursive(n) {  
  const response = n + 1;
  return response;  //반환
}

let answer = recursive(5);       //함수 호출
console.log(answer);             //출력 결과 : 6

 

그리고 이후에는 함수를 호출한 라인 아래의 코드들이 마저 실행될 것이다.

 

그렇다면 함수 내에서 다른 함수를 또 호출하는 함수가 있다면 어떨까?

"함수 A" 내에서 "함수 B"를 호출하고, "함수 B" 내에 "함수 C"를 호출하고 있다고 가정해보자. (재귀 함수 x, 재각기 다른 함수 A, B, C)

이미지 출처 -  http://10bun.tv/beginner/episode-4/

 

위 함수의 호출과 반환에서 말했듯이 함수 C의 정의된 로직들이 실행된 뒤 값을 반환하면, 시점은 함수 B에서 함수 C를 호출한 부분으로 넘어간다. 즉, 함수 C를 호출한 라인 이후의 나머지 코드들이 마저 실행된다는 뜻이다.

function B(){
	const returnOfC = C();
    // 나머지 코드
    
    return;
}

 

함수 B의 나머지 코드들이 실행되고 값을 반환한 뒤 함수 A에서 일어날 일들도 마찬가지다.

 

 

이제 위 내용을 기억한 상태로 재귀 함수를 살펴보자.

재귀 함수를 처음 접한 사람이라면 재귀 함수가 본인의 가장 처음으로 돌아가 코드를 되풀이한다고 오해하기 쉽다.

 

하지만 함수를 호출할 때마다 콜 스택 메모리를 잡아먹는다고 말했듯이 호출된 재귀 함수들은 모두 다른 메모리에 존재하며, 이렇듯 모습만 똑같은 서로 다른 존재다.

 

 

처음 살펴본 "함수의 호출과 반환에서의 데이터 흐름"과 "재귀 함수가 호출한 자신들이 서로 독립된 함수들" 이란 사실을 인지하면 재귀 함수가 아래 그림과 같이 동작함을 알 수 있다.

이미지 출처 -  http://10bun.tv/beginner/episode-4/

 

 

 

4. 인사이트

 

나는 처음 팩토리얼 구현을 통해 재귀 함수를 접했었다. 하지만 그때 당시 나는 재귀 함수를 반밖에 이해하지 못했었다.

 

탈출 조건에 도달하는 것까지만 이해를 해도 무리없이 구현이 가능했기 때문이다.

 

 

그러다가 백준의 4779 번 칸토어 집합이란 문제를 접하게 되었고, 재귀 함수의 탈출 이후 동작들에 대한 이해의 필요성을 느꼈다.

 

이후에도 백트래킹, 분할과 정복, DFS 등과 같이 재귀 함수에서 파생된 알고리즘들을 접하면서 재귀 함수의 완전한 이해가 얼마나 중요한지 다시 한번 느낄 수 있었다.