팩토리얼과 피보나치 수열에서 재귀함수의 작동 방식

백준 10872번 풀이

백준 10870번 풀이

이 두 개를 풀면서 재귀함수라는 걸 써봤는데, 대체 함수를 정의하는데 자기자신이 들어가는데 이게 어떻게 돌아가는걸까? 한번 알아보자.

아 다음꺼요? 그거 별찍기로 시어핀스키 사각형 찍어야되던데? (참고: 프랙탈임)

팩토리얼

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이다. 그럼 이제 호출이 끝났으니 싹 다 곱하면 된다. 이중계승의 경우 2씩 빼기 때문에 n이 0일때와 1일때 둘 다 정의해줘야 한다. 한쪽만 정의하면 depth 에러뜸…

피보나치 수열

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

얘는 코드 돌아가는거 보여주는걸로 5번째 달랬더니 74단계나 걸려…

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

대충 이렇게 된다. 재귀가 끝나는 조건문을 만날때까지 계속 함수를 호출하고, 조건문을 만나면 호출을 끝내고 싹 다 계산한다고 보면 된다.