[python] 간단한 예제로 알아보는 재귀함수

11월에, 분명 얼마전에 재귀함수를 공부했는데 벌써 까먹은 느낌이 들어서 간단하게 복습을 해보았습니다.

 

저는 장기 기억력이 정말 안 좋아서 이렇게 복습을 틈틈히 해줘야 하는데 그게 어렵네요ㅎㅎ

 

그래서 직장에서도 저한테 복잡하거나 헷갈리는 일을 할 때 빠르게 할 수 있도록 매뉴얼을 만들어 두고 있어요

자주 있는 일이 아닌 일을 처리할 때 유용하게 쓰고있는 것 같아요

 

직장에서 지출 및 예산관리를 담당하고 있는데 예수금을 잡거나 카드 오사용으로 인해 카드사용대체를 한다든가 할때,

더존프로그램에서 캡쳐를 해서 설명을 붙여 저장해 두고 다음에 그런 일이 발생하면 다시 그 파일을 열어서 봅니다.

 

저장해둘 때는 '이런 경우가 또 있으려나'하면서 귀찮을 때도 많지만 해두면 분명 쏠쏠하게 쓰게 되더라구요

덕분에 그냥 지나갔던 부분들을 오래 기억할 수 있게 되어서 원래 이 일을 했던 선생님께도 설명드릴 때도 있었구요!

 

그래서 앞으로 블로그도 더 열심히 적으려구요! 퇴근하고 공부하는 거만 해도 시간이 빠듯해서 지금까지 몇 개 못 적었지만 그래도 내년에는 많이 기록해서 제가 다시 공부하고 싶을 때 볼 수 있는 좋은 매뉴얼이 되면 좋을 듯 해서요ㅎㅎ

 

더 쓰면 재귀함수를 못 할 것 같으니 이만 줄이고 얼른 해볼게요!

 

 

1. 재귀함수(recursive function)란?

재귀함수는 함수 내에서 자기자신을 다시 호출하는 함수를 말합니다.

기존에 봐왔던 함수랑 어떻게 차이가 있는지 아래에서 확인하시면 이해가 빠르게 될거에요

# 1.많이 봐온 함수(보통의 사용자정의함수)
def func():
	pass
func()

# 2. 재귀함수
def recursive():           # 정의: 보통의 사용자 정의 함수와 다르지 않다
	recursive()        # 자기 자신을 함수 안에서 다시 호출(=재귀호출)
recursive() 		   # 첫 호출: 보통의 사용자 정의 함수와 다르지 않다.

 

 

2. 재귀함수의 구조

재귀함수는 함수 정의부 안에 스스로를 호출하는 부분과 사이클을 멈추는 명령을 포함합니다.

이렇게 재귀함수을 사이클을 멈추게 하는 조건을 베이스케이스(base case)라고 합니다.

 

베이스케이스는 '재귀호출 과정 전체를 한꺼번에 중단시키는 지점'이 아니라 '더 이상 파고들어갈 수 없으므로 직전에 호출한 곳으로 되돌아가야하는 지점'을 뜻합니다. 

그러므로 반복문을 완전히 중단시키는 break와는 차이가 있어요

# 정상작동하는 재귀함수의 형태 (베이스케이스 있음)

def count_down(n):
	if n == 0:                # base case
    	return
    print(n)
    count_down(n-1)
    
 count_down(3)
 
 #================================================
 
 # 오류나는 코드 (베이스 케이스 없음)
 
def count_down(n):
	print(n)
    count_down(n-1)
    
 count_down(3)
 
 # 위 코드의 결과
 3
 2
 1
 0
 -1
 ...
 
 #==> 함수의 시작을부터 재귀호출 사이에 이 재귀함수를 멈출 수 있는 명령이 없으므로
 # 프로그램이 멈추지 않고 계속반복하여 RecursionError가 발생한다.

 

 

3. 재귀함수 예시 _1

함수 작동 순서대로 적어보도록 하겠습니다.

아래 사진과 코드 및 자동순서를 비교하면서 보면 이해하기 좋을 거 같아요

 

재귀함수 작동 순서 (출처: https://codepractice.tistory.com/92)

def factorial(n):
    if n == 0:                    # 1번 베이스 케이스  
        return 1                  # 2번
    a = n * factorial(n-1)        # 3번 자기자신 호출
    return a                      # 4번
    
print(factorial(3))

1) 1번 => 3번

n = 3 

a = 3 * factorial(2)

 

: factorial(2) 호출

 

2) 1번 => 3번

n = 2

a = 2 * factorial(1)

 

3) 1번 => 3번

n = 1

a = 1 * factorial(0)

 

4) 1번 => 2번

n = 0

return 1

 

: 베이스케이스에서 return을 만나면 자신을 호출한 곳으로 돌아갑니다.

즉 3)에 factorial(0)으로 돌아가 return값인 1을 치환한다고 보면 이해를 빠르게 할 수 있습니다.

 

5) 4번

n = 1

a = 1 * 1 = 1

 

: 1,2,3번이 모두 마무리가 되었으므로 비로소 4번이 작동하게 됩니다.

 

6) 4번

n = 2

a = 2 * 1 = 2

 

7) 4번

n = 3

a = 3 * 2 = 6

 

 

4. 재귀함수 예시_2

위 예시는 큰 수부터 곱해나갔다면 이번 예시는 작은 수 부터 곱해나가는 팩토리얼 함수를 보겠습니다.

작은 수 부터 곱하기 위해서는 파라미터가 두 개가 필요해요

def factorial_r(n,i=1):
    if n == i:                 #베이스케이스
        return n
    return i * factorial_r(n,i+1)

print(factorial_r(4))

# 결과
24

1) n = 4, i = 1

1 * facrotial_r(4,2)

 

2) n = 4, i = 2

2 * facrotial_r(4,3)

 

3) n = 4, i = 3

3 * facrotial_r(4,4)

 

4) n = 4, i = 4

베이스케이스 만남

==> return 4

 

5) 끝!

예시 1과 달리 자기 자신 함수를 호출하는 부분 다음에 return이 없다.

 

 

 

 

* 참조: 책 코딩강화파이썬(이규호,2019)