재귀함수

재귀는 단순히 '중첩된 호출'이기 때문에, 모든 중첩된 함수 중 '가장 내부에 중첩된 함수'가 가장 먼저 반환될것이다.

이해한게 맞다면 재귀함수를 사용하면 스스로를 재호출 하는 경우이기 때문에 stack의 개념과 비슷하다고 볼 수 있다. 그러면 출력이 LIFO로 진행된다.

별 출력

# 반복문 사용
for i in range(1,8):
    print(i * "★")
    
# 재귀함수
def star_print(n):
    if n == 0:
        return
    else:
        star_print(n-1)
        print('*' * n)
        
star_print(7)

1. star_print(7) → star_print(6)
2. star_print(6) → star_print(5)
3. star_print(5) → star_print(4)
4. star_print(4) → star_print(3)
5. star_print(3) → star_print(2)
6. star_print(2) → star_print(1)
7. star_print(1) → star_print(0)
8. star_print(0) → return
   리턴을 만나서 조건이 충족된다. 이제 7번부터 1번의 순서대로 print가 실행된다

pytutor를 통해서 내부동작을 확인할 수 있다

별 출력결과
★
★★
★★★
★★★★
★★★★★
★★★★★★
★★★★★★★

구구단 출력

# 반복문
for i in range(0, 10):
    if i == 0:
        print("구구단 2단")
    else:
        print(f'2 * {i} = {2*i}')

# 재귀함수
def multi_table_2(n):
    if n == 0:
        print("구구단 2단")
    else:
        multi_table_2(n-1)
        print(f'2 * {n} = {2*n}')
        
multi_table_2(9)

별 출력과 비슷하게 진행된다. 숫자를 넣고 계속 진행하다가 n이 0이 되면 '구구단 2단'을 출력한다. 그 다음부터는 multi_table(1)인 경우의 print, 2일경우 print.... 마지막 9까지 출력된다.

구구단 출력결과
구구단 2단
2 1 = 2
2 2 = 4
2 3 = 6
2 4 = 8
2 5 = 10
2 6 = 12
2 7 = 14
2 8 = 16
2 * 9 = 18

카운트 다운

# 반복문
for i in range(5,-1,-1):
	  if i == 0:
		    print("발사")
	  else:
		    print(i, end=' ')

# 재귀
def countdown(n):
    if n == 0:
        print('발사')

    else:
        print(n, end = ' ')
        countdown(n-1)  

countdown(5)

1. countdown(5)
   print(5, end = ' ')
   countdown(4)
   → 5
2. countdown(4)
   print(4, end =' ')
   countdown(3)
   → 5 4
3. countdown(3)
   print(3, end = ' ')
   countdown(2)
   → 5 4 3
4. countdown(2)
   print(2, end = ' ')
   countdown(1)
   → 5 4 3 2
5. countdown(1)
   print(1, end = ' ')
   countdown(0)
   → 5 4 3 2 1
6. countdown(0)
   print('발사')

→ 5 4 3 2 1 발사

카운트다운 출력결과
5 4 3 2 1 발사

짝수 구하기

제한사항 : 1<= n <= 100

# 반복문
for i in range(85,101):
	  if i % 2 !=1:
		    print(i, end = ' ')

# 재귀
def even_num(n):
  while n<101:
    if n % 2 != 0:  
      return even_num(n+1)
    else:
      print(n, end=' ')
      return even_num(n+1)
      
# 재귀 2
def even_num(n):
    if n == 100:
        print(100, end=' ')
    else:
        if n % 2 != 1:
            print(n, end=' ')
            even_num(n+1)
        else:
            even_num(n+1)

짝수인 경우에 print해주는데 1과 2 재귀에 print위치가 1,0의 차이에 따라 조금씩 다르다. 어쨌든 계속 스스로를 호출하면서 짝수만 구해준다

짝수 구하기 출력결과
86 88 90 92 94 96 98 100

재귀함수에서 중요한 점은 반복을 중지하는 조건을 추가해줘야한다. 그렇지 않으면 계속 반복되는 불상사를 겪을 수 있다. 파이썬에서 재귀 깊이 제한이 1000으로 되어있으므로 중지해주지 않으면 1000까지 가고 error가 난다.

그러나? 최대 재귀 깊이를 늘리고 싶다면

import sys
sys.setrecursionlimit(3500)

이런식으로 지정해주면 된다

참고 : 재귀함수에 대한 간단정리