재귀가 뭐냐고 물었을 때 어그부츠 장사하다가 설명하는 것을 포기했었다. 이에 그치지 않고 재귀함수에 대해 쉽게 설명할 수 있게 정리해 본다.

재귀함수란?

일단 한국어의 재귀라는 것에 대해서 알면 더 쉬워진다. 생각보다 네이밍을 직관적으로 짓기 때문에 어원을 찾고 머리에서 그림만 그릴 줄 안다면 절반은 이해했다고 본다. '본디의 곳으로 다시 돌아오는 것.'을 재귀라고 한다. 함수는 수직으로 진행이 된다. 했던 것을 다시 돌아 또 하지는 않는다. 재귀함수라는 것은 했던 것을 또 하려고 만들어진 이름처럼 보인다. 재귀함수에 대해서 알아보자.

어떠한 함수에서 자신을 다시 한 번 호출하여 작업을 수행하는 방식. 반복문을 사용하는 코드는 재귀로 표현이 가능하고, 반대로 재귀로 표현할 수 있는 코드는 반복문 사용이 가능함. 재귀함수를 사용한 시점부터 그 사용이 끝날 때까지 다음 명령은 수행되지 않으며, 반복적으로 임하는 것이기 때문에 항상 재귀함수를 탈출할 수 있는 탈출구를 만들어 두어야 한다.

1. 탈출할 수 있는 탈출구를 만들지 않으면 어떻게 되나요?
   생각해 보자. 어떠한 미로에 진입을 했다. 여러 가지 미션들을 전부 거치고 다음으로 가는 문을 발견해서 문을 열었는데, 내가 지금까지 왔던 미로랑 똑같은 곳이다. 그게 계속 반복이 된다. 무한대로. 다음 스테이지가 투명 유리 창에 아른거리는데 나는 했던 걸 똑같이 해야 된다. 할 수 있지. 할 수는 있는데 하기 싫다. 계속 반복하다가 뇌 기능이 멈춰 버릴지도 모른다. 컴퓨터도 똑같다. 작업 관리자로 꺼 줘야 된다. ㅋㅋ

2. 마트료시카랑 비슷하다고 하던데, 어떤 게 비슷한가요?
   마트료시카를 열어 보면, 자신과 똑같은 모습을 했지만 살짝 작은 놈이 나온다. 걔를 열면 자신과 똑같은 모습을 했지만 살짝 작은 놈이 나온다. 걔를 열면 자신과 똑같은 모습을 했지만 살짝... <이것만 놓고 봤을 때, 1 번의 뇌 기능 멈춰지는 미로가 생각이 나지 않는가? 계속해서 자기 자신과 마주하는 모습이 나오는데, 1 번의 미로와 다른 점은 회를 거칠 때마다 점점 작아진다는 것과 마지막엔 사탕이나 초콜릿 같은 어떠한 보상이 있다는 것이다. 그리고 이게 재귀함수의 특징이라고 할 수 있다.

회를 거칠 때마다 점점 작아진다는 것은 재귀함수를 돌릴 수 있는 횟수에 제한을 둔다는 것이다. 제한을 두지 않으면 마치 패턴처럼, 반복되는 미로처럼 계속 돌고 돌기 때문에 다음 명령을 수행할 수도, 그렇다고 함수가 끝나지도 않기 때문에 조금씩 작아지게 만들어서 끝낼 수 있게 만들어야 된다.
마지막엔 사탕이나 초콜릿 같은 어떠한 보상이 있다는 것은, 이 재귀함수(마트료시카)가 끝이 나면 어떠한 결과를 도출한다는 점과 같다. 뇌 빠지게 반복적으로 행동을 행했는데 보상이 없다? 거의 대모 일어나는 거거든요. 공장 알바 할 때 일급 안 주는 거랑 같은 이치거든요. (공장 알바 경험한 사람이라 매우 분노 중) 재귀함수는 '함수'이기 때문에 return 값이 필수적으로 있고, 그 리턴 값을 가지고 다시, 다시, 다시 자신을 통과하여 마지막으로 나온 리턴 값이 사탕이나 초콜릿처럼 달고 값지기 때문에 비슷하다고 할 수 있다. 있기 때문에 초콜릿 같은 보상과도 같다고 볼 수 있다.

재귀함수 예시

자바스크립트로 표현함

가장 대표적인 팩토리얼 예시

function fac(n) {
  if(n===1) {return 1}
  return n * fac(n-1)}

fac(5) //120

팩토리얼이란? 1부터 n까지 차례대로 곱한 값 (n!라고도 씀.)
5!를 구한다고 했을 때, 5 x 4 x 3 x 2 x 1로 표현할 수 있는데, 수가 하나씩 줄어들고 작아지는 게 마트료시카와 꽤 닮았다. 게다가 마지막엔 120이라는 값을 받기도 하니 사탕도 두둑이 챙길 수 있다.

위의 함수를 풀이했을 때,

fac(5)는
5 x fac(5-1) x fac(4-1) x fac(3-1) fac(2-1)

로 보여지게 되는데, 5 x fac(5-1)을 끝내고 20 x fac(4-1)로도 할 수 있지 않느냐? 라고 한다면 비슷해 보이지만 다르다고 말할 수 있다. 재귀함수가 호출이 되면, 재귀가 끝나기 전까지는 다음 명령을 호출할 수 없다는 특성 때문이다. 5 뒤로 나오는 fac 함수는 계속 쌓인다. 스택이 쌓인다고 볼 수 있다. (n이 1이 되면 멈추라고 하는 if문이 있기 때문에 n은 1에서 멈추고, 재귀함수에서 빠져나올 수 있다.)

fac(2-1)
fac(3-1)
fac(4-1)
fac(5-1)
5 *

이런 식으로 차근차근 쌓이게 된다. 그리고, 위에서부터 다시 차근차근 실행하며 곱해 주는 것이다. 결론적으로는 5 x 4 x 3 x 2 x 1를 하게 되는 것.

어차피 했던 것을 또 해 주는 것이기 때문에 앞서 말했던 것처럼 반복문으로도 풀 수 있다.

function fac(n) {
  let j = 1;
  for(let i = 1; i<=n; i++) {
    j = j * i;
    return j
  }
  
fac(5) //120

i의 값이 n과 같아질 때까지 반복문을 실행하는 것으로 제한을 뒀고, i는 1부터 1씩 증감하며, 그 값을 j라는 변수에 담았다. (j는 1이어야 한다. 그냥 변수 선언만 해 주면 숫자라는 것을 모르고, 0이라고 하면 곱셈이기 때문에 계속 0이 되기 때문.)
반복문에서는 1 x 1, 1 x 2, 2 x 3, 6 x 4, 24 x 5의 순서로 차근차근 계산해나간다.
1 x 2 x 3 x 4 x 5를 하게 되는 것. (물론 5에서부터 하나씩 줄어들게 할 수도 있다.)

앞서 말했던 것처럼 어떠한 것을 반복하려고 할 때는 재귀와 반복문, 둘 다 사용이 가능하다. 그렇다면,

위의 두 예시가 알려 주는 재귀함수와 반복문의 장,단점은 무엇일까?

재귀함수의 장점: 직관적이다. 반복문보다 코드가 깔끔하다. 변수 사용이 줄어든다.
반복문의 장점: 재귀함수보다 쉽다.(ㅎㅎ) 원하는 것만 알차게 반복할 수 있다. 재귀보다 빠르다.
재귀함수의 단점: 메모리가 많이 든다. 함수 자체를 다시 돌리는 것이기 때문에, 팩토리얼처럼 단순한 계산이 아닌 피보나치나 조금 더 복잡한 계산을 하게 되어 함수가 커지게 되면 계산할 것들이 많아지게 되고, 느려지고, 메모리 소비가 크다.
반복문의 단점: 재귀보다 직관적이지 않다. 쓸데없는 변수를 사용하게 된다. 코드 길이가 길어진다.

그러므로, 재귀와 반복문의 장단점을 파악하여 적재적소에 쓸 수 있어야 한다. 재귀로 시작했지만 끝은 재귀와 반복문인 이유가 여기에 있다. 재귀가 더 예쁘고 좋아 보이고, 반복문을 대체할 수 있고, 코드를 봤을 때 굉장히 쉬워 보이는데 재귀만 쓰는 게 낫지 않을까요?(내가 그런 생각을 했음.)라고 생각할 수 있는데, 어떠한 게 자신에게 맞고 특출나게 좋아서 그것만 쓰는 것은 좋지 않다. 각각의 장단점이 있기 때문에 그들이 최상의 컨디션을 지킬 수 있는 자리에 알맞게 놓아 주는 게 효율적인 코드를 작성하는 데에 있어서 좋지 않을까 하는 생각을 하고 있다. ㅎㅎ

개인적으로 재귀는 어떠한 값을 바꾼 상태로 함수를 실행하고 싶을 때 쓰는 게 가장 예뻐 보인다.

functin foo(a, b) {
  if(a !== 5) {return foo(5, b)}
  return a + b}
foo(1,2) //7
//진짜 쓸데없는 함수이고 사용해서도 안 되지만.. 이런 식으로 어떠한 것을 미리 바꿔 놓고 함수를 실행하게 하는 게 제일 좋다.

틀린 부분이 있거나 첨언하고 싶은 내용이 있다면 댓글로 말씀해 주세요. 공부하는 데에 도움이 됩니다.

---

참고 문서
https://marobiana.tistory.com/79
https://gomguard.tistory.com/111