재귀함수가 돌아가는 방식을 알아보자

재귀함수는 정의할 때 자기자신을 재참조한다고 했는데, 정의하는데 자기자신이 들어가면 대체 어떻게 돌아가는지 알아보자. 라이츄가 라이츄를 꺼내고 그 라이츄가 라이츄를 꺼내고 

---

팩토리얼

def factorial(n):
  if n == 0:
    return 1
  return n * factorial(n-1)

5!을 저걸로 계산하게 되면 

1. factorial(5) = 5 * factorial(4)
2. factorial(4) = 4 * factorial(3)
3. factorial(3) = 3 * factorial(2)
4. factorial(2) = 2 * factorial(1)
5. factorial(1) = 1 * factorial(0)
6. factorial(0) = 1
7. 오케이 가릿

여기까지 왔더니 factorial(0)이 1이네? 그럼 호출 중단하고 싹 다 곱하면 된다. 이중계승의 경우 홀수와 짝수의 종착점이 다르기때문에 n이 0일때와 1일때 둘 다 정의해줘야 한다. 

 

피보나치 수열

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

 

코드 돌아가는거 보여주는걸로 돌렸더니 74단계 걸린거 실화다. 

1. 피보나치(5) = 피보나치(4) + 피보나치(3)
2. 피보나치(3) = 피보나치(2) + 피보나치(1)
3. 피보나치(1) = 1
4. 피보나치(2) = 피보나치(1) + 피보나치(0)
5. 피보나치(0) = 0
6. 오케이 가릿 

대충 이런 느낌이다. 재귀가 끝나는 조건문을 만날때까지는 계속 함수를 호출하고, 재귀가 끝나면 싹 계산하는 방식.