재귀함수 (Factorial)

 재귀햠수?

cs에서 재귀란 자기를 선언할 때 자기 자신을 다시 참조하는 것을 뜻합니다.

프로그래밍에서 재귀함수는 자기 자신이 함수 내에서 호출하는것을 말합니다

재귀함수는 꼭 종료 조건을 가지고 있어야 합니다. 파이썬 같은 경우 

재귀 호출이 3000번을 초과하게 되면 RecursionError가 발생합니다.

 

 

간단하게 사용해보기

어디서든 재귀 함수를 찾아보면 십중팔구 따라오는 게 하노이탑과 팩토리얼이죠

더 대중적인 팩토리얼을 사용해보도록 하겠습니다.

 

 

팩토리얼이란

n!로 표현하며 1부터 n까지의 곱을 말합니다.

 

반복문을 이용한 팩토리얼

이걸 재귀적으로 바꿀 거예요

재귀함수를 이용한 팩토리얼

처음 보면 저게 뭐지 할 수도 있는데 원래 어려운 내용입니다.  (나만 어려울 수도 있고)

Factorial(5)를 했다면

내림차순(54321)으로 생각하지 않고 오름차순(12345)으로 생각해보면 간단합니다

n-1 n-1 n-1 쭉쭉 내려가서  2까지 내려간다면

2 * 2-1이니까

2 * Factorial(1) n이 1이면 1을 return 하니까

2*1 = 2

facktorial(2) = 2

근데 얘를 호출한 애는 factorial(3)일 테니까 factorial(2)는 2로

3 * facktorial(2) = 3*2

근데 또 얘를 호출한 애는 4죠?

그럼 4 * facktorial(3) 

facktorial(3)은 6

이런 식으로 1부터 시작해서 5까지 

곱한걸 리턴해주는 거죠

 

팩토리얼 말고 1부터 n까지 더한걸 리턴해주는 재귀함수도 만들어보겠습니다.

이제 이건 그냥 이해가 되죠

 

재귀 함수는 반복문이나 기초문법처럼 대충 감으로 떼고 대충 이거구나

하고 넘어가면 볼 때마다 이해가 안 갑니다.

그래서 확실히 알고 넘어가 야한 부분 같습니다.

 

재귀 함수를 쓰면 좋은 점

팩토리얼을 반복문으로 구현한 것과

재귀 함수로 구현한 것만 봐도

변수의 선언을 하지 않고 코드가 간결해진다는 것을 확인할 수 있습니다.

 

재귀 함수 단점

1. 반복문보다는 시간 복잡도(BigO)를 계산하기 조금 번거롭다는 점

2. 재귀 함수를 사용하게 되면 갑자기 코드가 간결해지지만 본인이 아닌 다른 사람이 보게 되면 이해하는데 시간이 좀 걸릴 수 있습니다.

3. 메모리를 많이 먹습니다 잘못 사용하게 되면 속도가 느려질 수 있음

4. 종료 조건을 확실하게 하지 않으면 무한반복이 걸릴 수도 있습니다. 반복문도 마찬가지 긴하죠

 

단점들을 보면 잘 모르고 쓰다가는 대참사가 일어날 수 있다는 걸 볼 수 있습니다.

그니까 재귀 함수 대충 배우고 협업할 때나 실무에서 쓰지 않는 게 좋겠죠.

잘 모른다면  되도록이면 반복문으로 해결하는 걸 추천드립니다.