[파이썬] 재귀 함수(Recursive Function)

2023.02.18 코드잇 학습내용 정리

 

재귀 (Recursion)

재귀란 '자기 자신을 호출하는 것'

 

재귀 함수 (Recursive Function) 

자기 자신을 호출하는 함수

 

재귀함수 예1

 

🔎 팩토리얼

재귀적으로 문제를 푼다는 것은 같은 형태의 더 작은 문제(부분 문제 ; sub problem)를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것을 말함  

 

아래와 같이 f(n)을 구하기 위해 f(n-1)의 값을 이용하는 것처럼 규칙을 찾아서 문제를 푸는 것

f(5) = 5! = 5 * 4 * 3 * 2 * 1 = 5 * 4! = 5 * f(4) 
f(4) = 4! = 4 * 3 * 2 * 1 = 4 * 3! = 4 * f(3)
f(3) = 3! = 3 * 2! = 3 * f(2)
...
f(n) = n! = n * (n-1)! = n * f(n-1)
단, n=0일 경우는 1

 

재귀 함수 문제를 풀 때는 항상 base case와 recursive case로 경우를 나누어주어야 함

base case 즉, 탈출 조건이 있어야 함수를 끝낼 수 있음

base case란 문제가 충분히 작아서 바로 풀 수 있는 경우를 말함 (따로 풀어야 하는 부분 문제가 없는 경우)

재귀 함수에서 base case를 정의하지 않으면 함수가 끝나지 않음

 

위의 팩토리얼 문제에서

base case    :    n = 0인경우 n! = 1 

recursive case   :    n > 0인 경우 n! = (n-1)! X n

 

재귀함수 사용하여 팩토리얼 풀기

 

🔎 재귀 함수 vs 반복문

반복문으로 풀 수 있는 문제는 재귀 함수로 풀 수 있고, 재귀 함수로 풀 수 있는 문제는 반복문으로 풀 수 있음

 

그러나 재귀 함수에도 단점이 있음 

재귀 함수에서는 동일한 함수를 계속해서 호출할 때마다 함수를 위한 메모리가 계속해서 할당됨. 함수가 호출될 때마다 사용되는 임시 저장 메모리를 콜 스택(call stack : 함수가 끝난 위치를 기록해 두는 것)이라고 부름. 재귀 함수를 사용했을 때 무한루프에 빠지거나 재귀 함수 호출이 너무 많으면 콜 스택이 쌓이면서 스택 공간이 초과되는 스택 오버플로 오류 (StackOverflowError)가 발생. 파이썬에서는 콜 스택을 1000개 까지만 허용함

 

반복문을 쓰는 게 더 깔끔하거나 효율적일 때가 있고, 재귀 함수를 쓰는 게 더 깔끔하거나 효율적일 때가 있는데 상황에 따라 적절히 사용하고, 콜스택이 쌓이는 문제가 예상되면 반복문을 사용

 

🔎 피보나치 수열

재귀 함수 작동 FLOW

i == 1 : fib(1)
return 1

i == 2 : fib(2)
return 1

i == 3 : fib(3)
fib(1) + fib(2) = 1 + 1 = 2

i == 4 : fib(4)
fib(2) + fib(3) = 1 + 2 = 3

...

i == 10 : fib(10)
fib(8) + fib(9) = 55

콘솔 출력값

1
1
2
3
...
55

 

🔎 n의 각 자릿수의 합 구하기

▼▼ 내가 작성한 코드 : sum_counts 를 재귀 함수로 사용

숫자 n을 문자열 n으로 변환 → str_n
n의 자릿수 계산 → count_digits
 
문자열로 변환한 n의 맨 뒷자리에서부터의 합을 구하는 함수 : sum_counts
base case : 1자릿수 일때 (count_digits == 1일 경우)에는 str_n[0] return
recursive case : 2자릿수 이상인 경우 각 자릿수의 합 더하기

sum_digits(n)에 대하여 sum_counts(자릿수) return  

예 :

n = 22541

str_n = "22541"
count_digits = 5

sum_counts(5) return

sum_counts(4) + int("22541"[4]) = sum_counts(4) + 1 = 13 + 1 = 14
sum_counts(3) + int("22541"[3]) = sum_counts(3) + 4 = 9 + 4 = 13
sum_counts(2) + int("22541"[2]) = sum_counts(1) + 5 = 4 + 5 = 9
sum_counts(1) + int('22541"[1]) = 2+2 = 4
sum_counts(1) = int("22541"[0]) = 2

(파란색은 윗방향으로 진행되는 과정)

내가 작성한 코드

 

▼▼ 모범 답안 : // 와 % 활용하여 쉽게 작성할 수 있음

base case
n이 10보다 작으면 n return

recursive case
sum_digits(22541) → 22541 % 10 + sum_digits(22541 // 10) = 1 + sum_digits(2254) = 1 + 13 = 14
sum_digits(2254) → 2254 % 10 + sum_digits(2254 // 10) = 4 + sum_digits(225) = 4 + 9 = 13
sum_digits(225) → 225 % 10 + sum_digits(225 // 10) = 5 + sum_digits(22) = 5 + 4 = 9
sum_digits(22) → 22 % 10 + sum_digits(22 // 10) =  2 + sum_digits(2) = 2 + 2 = 4
sum_digits(2) → 2 return

모범답안

 

 

🔎 리스트 뒤집기

규칙 찾기
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]

9 + [1, 2, 3, 4, 5, 6, 7, 8 뒤집기]
      8 + [1, 2, 3, 4, 5, 6, 7 뒤집기]
             7 + [1, 2, 3, 4, 5, 6 뒤집기]
                    ...
                        2 + [1 뒤집기]

[ 뒤집기] → flip(some_list[ :1]

 

🔎 하노이의 탑

규칙찾기

기둥은 총 3개 → start_peg = 1, end_peg = 2

만약 원판이 없다면, 함수는 그대로 끝남
if num_disks == 0 : return

원판이 1개라면,
1번 원판을 1번 기둥에서 3번 기둥으로 이동

원판이 2개라면,
1번 원판을 1번 기둥에서 2번 기둥으로 이동
2번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 3번 기둥으로 이동

원판이 3개라면,
1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동    → 원판 2개일 때와 같음. 단 2번 기둥으로 이동하는 것만 다름
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동    → 원판 2개일 때와 같음. 단 2번 기둥에서 3번 기둥으로 이동해야 함
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

...

원판이 num_disks라면,
1번부터 num_disks - 1번까지의 원판을 1번 기둥(start_peg)에서 2번 기둥(other_peg)으로 이동
num_disks의 원판을 1번 기둥(strart_peg)에서 3번 기둥(end_peg)으로 이동
1번부터 num_disks - 1번까지의 원판을 2번 기둥(other_peg)에서 3번 기둥(end_peg)으로 이동

이를 코드로 작성하면,

hanoi(num_disks - 1, start_peg, other_peg)
move_disk(num_disks, strat_peg, end_peg)
hanoi(num_disks - 1, other_peg, end_peg)

여기서 start_peg = 1, end_peg = 3, other_peg = 2 → 세 개의 합은 6
따라서 other_peg = 6 - start_peg - end_peg

실행 과정 정리