Recursive Functions

재귀 함수(Recursive Functions)는 자기 자신이 리턴 값인 함수다. 재귀라는 단어는 잘 사용하지 않는 단어라 영어 단어가 훨씬 더 직관적으로 보일 정도다. 한자어인 만큼 한자를 알면 사실 쉽다. 두 재 혹은 다시 재(再)와 돌아갈 귀(歸)다. 다시 돌아간단 뜻이다. 단어를 왜이렇게 길게 설명했느냐 묻는 다면, 이 함수는 이게 핵심이고 전부기 때문이다.

 

함수를 다시 리턴한다는 건 반복한다는 소리다. 즉, 반복문의 역할이라고 이해하면 좋다. 반복을 함수로 할 뿐인 셈. for문과 재귀함수를 비교하며 살펴보자. 반복의 대명사 팩토리얼로 비교했다.

// for문을 이용한 팩토리얼

let n=4
let result=1

for (let i = n; i >= 1; i--) {
  result = result * i;
}

console.log(result) // 24

팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말한다. 위 코드는 4팩토리얼(4!)이 주어졌다고 가정했다. 결과는 24. 잘 작동한다. 4에서부터 시작해 하나씩 숫자를 내려가면서 1까지 모두 곱했다. 반복문을 살펴보면, 초기값이 있고 반복할 조건 값, 그리고 증감문이 있음을 기억한 후 재귀함수로 넘어가보자.

// 재귀함수 팩토리얼
function factorial (n) {
  if (n === 1) return 1; 
  return n * factorial(n - 1);
}

factorial(4); // 24

재귀함수로 작성한 팩토리얼이다. 4!의 결과로 24가 나왔으므로 잘 작동하는 코드다. 재귀함수는 return 값으로 자기 자신을 넣는다고 표현했듯 실제로 자기 자신이 return에 들어 있음을 알 수 있다. 리턴에 자기 자신이 있는 부분, 이 부분이 반복문처럼 작동하게 한다. 함수를 살펴보면 if문이 있다. 이게 반복문에서 반복 조건과 같다. for문을 반복 조건없이 돌려본 분이 계시다면, 바로 이해할 수 있다. 무엇으로 실행하느냐에 따라 다르지만 SyntaxError 아니면, 무한 루프에 빠진다. 재귀 함수도 마찬가지다. 조건문이 없다면 바로 무한 루프로 빠지며 해당 프로그램을 강제 종료하는 자신의 모습을 볼 수 있다. 

위 코드는 숫자 4가 주어졌을 때 4 * factorial(4-1)을 리턴한다. 그럼 factorial(3)이 되고 이는 함수이므로 3 * factorial(3-1)을 리턴한다. 이는 결국 4 * 3 * factorial(3-1)이 된 셈이다. 그럼 factorial(2)는? 당연히 실행되고 4 * 3 * 2 * factorial(2-1)로 연산한다. factorial(2-1)은 factorial(1)이다. 여기서 n === 1 조건문에 걸린다. 그리고 자기 자신을 호출하는 리턴이 아닌 1을 리턴하게 되어 재귀할 수 없게 된다. 그럼 여기까지 완성된 4!의 return은 4 * 3 * 2 * 1이며, 24라는 값을 출력한다.

이로서 재귀함수도 반복문의 역할과 같다는 점을 봤다. 그렇다면, 반복문이든 재귀함수든 마음에 드는 걸 아무때나 골라 써도 될까? 그것은 한 번 더 생각해 봐야할 문제다.

 

Recursive & Iterative

재귀와 반복은 돌고 돈다는 점에서 같지만, 두 가지가 컴퓨터에서 어떻게 실행되는 지까지 알아야 선택 시 수월하다. 물론 대부분의 경우 재귀 함수로 풀 수 있는 것을 반복문으로 풀 수 있고, 그 반대도 마찬가지다. 거기다가 종류의 따라 반복문이 이해하기 쉽거나, 재귀함수가 이해하기 쉬울 수도 있다. 다만, 그게 전부가 아님을 알아야 한다는 뜻이다. 결론을 말하자면 메모리 때문이다.

 

재귀함수와 메모리

반복문은 메모리 힙 영역을 사용하는 반면, 함수는 메모리 스택 영역으로 사용한다. 간단히 얘기하자면, 힙 영역은 메모리 크기 제한이 없고, 스택은 크기가 제한되어 있다. 함수가 실행되면 메모리에 스택 단위로 쌓인다. 선입후출, 즉 FILO다. 재귀함수는 자기 자신을 호출함으로 함수를 반복적으로 실행한다. 새 변수에 매개 변수 집합이 메모리에 계속 생긴다. 4!이면 4개면되지만, 만약 숫자가 100!이라면? 100개 스택이 쌓이는 셈. 여기서 만약 멈추는 조건문이 없다면?! 우리에게 익숙한 단어인 그 것. 스택오버플로우가 발생한다. 스택이 받아들일 수 없는 이상의 스택이 쌓이면 메모리가 멈추며 오류를 내는 것.

 

반복문과 재귀함수 단순 비교

	반복문	재귀함수
기본	일련의 명령을 반복적으로 사용.	함수 자체를 호출.
체재	반복 시 초기화, 조건, 루프 내 명령문 실행 및 제어 변수 업데이트 포함.	보통 종료 조건만 지정(조건 추가 가능).
종료	특정 조건에 도달할 때까지 반복 실행.	조건문은 함수 호출을 본문에 포함. 재귀 호출을 실행하지 않고 함수를 강제로 반환.
조건	제어 조건이 참이라면 무한 반복.	조건에 수렴하지 않으면 무한 재귀.
무한반복	무한 루프는 CPU 사이클을 반복적으로 사용	무한 재귀는 스택오버플로우를 일으킴
스택 메모리	사용하지 않음.	사용함(스택오버플로우 가능성).
속도	상대적으로 빠름	상대적으로 느림
가독성	코드가 길어질 확률 높아 가독성 떨어짐.	사용 변수가 적어 상대적으로 가독성이 높을 가능성 있음.

표 출처 : https://hazel-developer.tistory.com/173

 

마무리

재귀함수를 공부하다가 메모리까지 갔다. 가볍게 생각했다가 궁금함을 타고타고 가다보니 메모리 작동 방식을 보고 있는 나를 발견했다. 작동 방식을 알고나니 재귀 함수랑 반복문중 '난 이게 편해'라고 무작정 선택할 부분이 아닌 듯했다. 간단한 웹이나 프로그램은 상관 없겠으나, 서비스 규모가 크다면 지난번 전역 상태 관리처럼 속도와 비용 면에서 큰 차이가 날 듯하다. 

아, 작동 원리를 이해하고 나니 알고리즘 문제 풀 때 사람들이 왜 for문이 빠르다고 하는 지 이해했다. 메모리의 사용 영역에 따른 차이라니,,,  생각지도 못했다. 그냥 다 CPU가 연산하는 줄 알았다. 이래서 알면 알수록 더 잘 사용하게 된다고 하는 듯하다. 물론 잘 사용하게 됐다는 의미는 아니다. 공부하면서 느끼는 건 여전히 모르는 것들 투성임을 알게 될 뿐. 틈틈히 더 공부해야만 하는 이유가 늘어난다:)

 

[MDN] Recursion

[MDN] 루프와 반복

재귀(Recursive)와 반복(Iterative)

재귀함수 (Recursive Function) 란?

※ 잘못된 내용이 있을 경우 댓글로 알려주세요. 배우고 익히고 수정하겠습니다:)