재귀함수

재귀란 원래 자리로 되돌아가는 뜻을 가지고 있다.

재귀함수를 쓰는 방식은 주어진 문제를 해결하기 위해 하나의함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식을 말한다.

재귀함수가 아닌 반복 방식으로 문제를 충분히 해결할 수 있다.
따라서 반복문이나 재귀함수를 쓰는 것은 개발자의 선호에 따라서 쓰면 되겠다.

def countdown(number) :
  print(number , "!!")

countdown(3) #3 !!
countdown(2) #2 !!
countdown(1) #1 !!
countdown("발사") #"발사!!""

결과

3 !!
2 !!
1 !!
발사 !!

• 해당 함수를 반복문으로 작성해보자

def countdown(number) :
  print(number , "!!")

for i in range(10,0,-1) :
  countdown(i)

countdown("발사")

10 !!
9 !!
8 !!
7 !!
6 !!
5 !!
4 !!
3 !!
2 !!
1 !!
발사 !!

• 해당 함수를 재귀함수로 작성해보자

def countdown(n) :
  if n==0 :
    print("발사 !!")
  else : 
    print(n,"!!")
    countdown(n-1)

countdown(10)

10 !!
9 !!
8 !!
7 !!
6 !!
5 !!
4 !!
3 !!
2 !!
1 !!
발사 !!

n-1 혹은 n+1 만큼의 인수를 더한 함수를 호출한다. 호출되는 동안의
그 함수명의 반환값은 대기상태로, 아직 정해지지 않은 값이 된다.

이전에 호출한 함수의 주소를 알아야 재귀함수가 정상적으로 작동한다.

요즘 프로그래밍 언어는 메모리의 저장 공간이 좋아져서 호출되는 함수의 메모리 주소를 기억하게 만들기 때문에 그 부분에서는 별 문제가 없다.

재귀함수를 쓸 때 주의해야할 점

• 루프문을 완벽히 제어하지 못한다면 예상치 못한 결과를 초래할 수 있다.

def countdown(n) :
  if n==0 :
    print("발사 !!")
  else :
    print(n,"!!")
    countdown(n-1)

countdown(-2)

-2 !!
-3 !!
-4 !!
.
..
...
-946 !!
-947 !!
-948 !!
-949 !!
-950 !!
-951 !!
-952 !!
-953 !!
-954 !!
-955 !!


---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
/usr/lib/python3.10/threading.py in _wait_for_tstate_lock(self, block, timeout)
   1115         try:
-> 1116             if lock.acquire(block, timeout):
   1117                 lock.release()

RecursionError: maximum recursion depth exceeded while calling a Python object

During handling of the above exception, another exception occurred:

RecursionError                            Traceback (most recent call last)
2 frames
... last 1 frames repeated, from the frame below ...

<ipython-input-82-eac54e3be8aa> in countdown(n)
      4   else :
      5     print(n,"!!")
----> 6     countdown(n-1)
      7 
      8 countdown(-2)

RecursionError: maximum recursion depth exceeded while calling a Python object



#이 코드는 결국에는 함수의 호출이 반복되는 무한 루프가 된 걸 볼 수 있겠다.

• 재귀함수는 함수의 호출이 끝나는 시점에서 되돌아가는 것을 명심하자

def countdown(n) :
  if n>99 :
    n=n-1
    print("한도에 도달했습니다.")
  elif n>0 : 
      countdown(n+1)
    
      print(n)
    


countdown(10)

한도에 도달했습니다.
99
98
97
96
95
94
93
92
91
90
89
88
.
..
...
17
16
15
14
13
12
11
10

• 다음은 countdown() 함수의 재귀호출을 표현한 것이다

countdown(11) · · · · · ·

countdown(100) <함수 호출의 끝>
출력 : print("한도에 도달했습니다.")