Python

Recursive function

python, recursive function
  • 재귀 함수(recursive function, recursion)
  • 자기가 자기 자신을 호출하는 함수
  • 기저 조건(base case) = 종료 조건, 탈출 조건

  1. Basic

    • 기저 조건을 반드시 정해줘야 한다.(종료, 탈출)
    • 재귀하는 과정에서 자기 자신을 만날 때마다 blocking이 걸린다.
    • blocking이 걸린 다음에 함수가 호출되며 stack frame에 쌓인다.
    • 함수가 쌓일 수 있는 stack frame 공간이 정해져 있다.
    • 정해진 stack frame을 넘어버리면 stack overflow가 발생한다.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      def func(num):
          # 기저 조건(base case)
          # 종료 조건
          # 탈출 조건
          if num <= 0:
              return
          
          print(num, end = ' ')
          func(num - 1)

      func(5)
      >> 5 4 3 2 1

  2. Basic function example

  • factorial(계승)

    • 점화식 –> fac(num) = fac(num - 1)*num
    • 기저 조건 –> if num == 1 return 1
      1
      2
      3
      4
      5
      6
      7
      8
      def factorial(num):
          if num == 1:
              return 1
          return factorial(num - 1) * num

      for num in range(1, 10):
          print(factorial(num), end = ' ')
      >> 1 2 6 24 120 720 5040 40320 362880

  • fibonacci(피보나치)

    • 점화식 : fibo(n) = fibo(n - 2) + fibo(n - 1)
    • 기저 조건 : if n == 1 or n == 2 then return 1
      1
      2
      3
      4
      5
      6
      7
      8
      def fibonacci(n):
          if n == 1 or n == 2:
              return 1
          return fibonacci(n - 2) + fibonacci(n - 1)

      for n in range(1, 10):
          print(fibonacci(n), end = ' ')
      >> 1 1 2 3 5 8 13 21 34
Share