[python/자료구조] 재귀함수

 

재귀함수란?

---

메소드 혹은 함수의 내부에서 자기 자신을 다시 호출하는 함수이다.

• 재귀함수를 통해 코드를 보다 간결하게 작성할 수 있으며 변수 사용을 최소화할 수 있다.
• 모든 재귀함수는 반복문을 통해 동일한 기능을 구현할 수 있다.
• 함수를 연속적으로 호출할 경우 메모리 내부 스택 프레임에 쌓이며 대표적으로 DFS를 간결하게 작성할 수 있다. 

 

 
  def recur_fun(cnt):
      print('{}번째 재귀함수 호출'.format(cnt))
      if cnt <= 5:
          cnt += 1
          recur_fun(cnt)
      else:
          return

  if __name__ == '__main__':
      cnt = 0
      recur_fun(cnt)
       

< 출력 결과 >

1번째 재귀함수 호출
2번째 재귀함수 호출
3번째 재귀함수 호출
4번째 재귀함수 호출
5번째 재귀함수 호출
6번째 재귀함수 호출

 

---

 

문제 ) 주어진 data 리스트 요소들의 합으로 표현할 수 있는 숫자의 경우의 수는? 

 

1. 반복문을 통한 완전 탐색

  
  data = [ 2, 4, 6 ]

  result = set( )
  for i in range(2):
      for j in range(2):
          for k in range(2):
              result.add( data[0] * i + data[1] * j + data[2] * k )
  print(result)
   

< 출력 결과 >

{0, 2, 4, 6, 8, 10, 12}

 

2. 재귀함수를 활용한 완전탐색

  
  def recur( index, value ) :
      if index == len( data ) :
          result.add( value )
      else :
          recur( index+1, value +data[index] )
          recur( index+1, value )

  if __name__ == '__main__':
      data = [ 2, 4, 6 ]
      result = set( )
      recur( 0,0 )
      print( result )
       

< 출력 결과 >

{0, 2, 4, 6, 8, 10, 12}

 

---

재귀함수 활용

 

1. 팩토리얼

 
  def fac(n):
      if n <= 1 :
          return 1
      else :
          return n * fac(n-1)
           

 -> 자연수의 n값이 주어질 때, 1에서 n까지의 모든 자연수의 곱을 말한다.

ex ) fac(3)  ->  3 * 2 * 1  -> 6

 

2. 피보나치 수열

 
  def fac2(n):
      if n < 2 :
          return n
      else :
          return fac2(n-1) + fac2(n-2)
           

-> 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. 

ex ) fac2(5) -> 1 + 1 + 2 + 3 + 5 = 8