사진: Unsplash의Kalle Kortelainen
재귀함수 배워야 하는 이유
- 재귀함수는 자료구조 수업에서 이후 배울 고급 정렬, 동적 계획법에서도 등장한다.
- 변수의 개수를 최소화할 수 있다. 출처
머리 빠지게 변수명 고민하지 않아도 돼서 좋은 것 같다. 하지만 불편함이 더 크므로 장점이라고 보기엔 못마땅하다. - 재귀함수로 푸는 것이 더 직관적인 문제가 있다. 귀납적 문제인 하노이의 탑, 피보나치 수열, 팩토리얼이 대표적이다. 이들 모두 점화식으로 정의가 되는데, 점화식은 구하고자 하는 항의 이전 항들로 항의 값을 구하는 식이다. 재귀의 정의인 무언가를 설명할 때 자기를 포함한 것이라는 측면에서 일맥상통한다. 하나의 함수(점화식)에 이전(n-1번째 항)의 입력값을 넣어 나온 결과를 사용해 이후 항(n번 째 항)의 결과를 구한다는 것. 쯤으로 이해할 수 있을 것 같다.
(예시 1 피보나치 수열의 점화식)
f(n-1) + f(n-1) = f(n)
- 알고리즘적 측면에서 보자면 재귀적 사고방식을 평소에 연습하는 것이 매우 중요하다고 한다. 출처
왜 그냥 보면 O(n)이고, 재귀적인 관점에서는 O(logn)일지는 한 번에 와닿질 않아서 재귀를 다 이해하고 다시 돌아와야겠다. ❓
재귀함수 예제와 코드 파헤치기
재귀함수란?
재귀함수는 자기 자신을 참조하는 함수이다. 함수를 정의할 때 아직 완성되지 않은 함수를 함수 안에서 사용하는 희한한 구조인데 가장 어려운건 함수가 완성된 것으로 믿는 것(?)이다. 다음은 예제이다.
문제 1.
재귀(recursion)를 이용하여 1부터 n까지의 자연수를 한줄에 하나씩 출력하는 함수를 작성하시오.
주의) 반드시 재귀를 이용하고 반복문(while, for 등등)을 사용하지 않는다.
결과
1
2
3
4
==========
1
2
3
4
5풀이
def count_up(n):
n을 입력하면 1부터 n까지 개행을 포함하여 출력하는 함수이기 때문에 '숫자 위로 세기'의 의미를 가지고 있는count_up()으로 명명한다.
if n == 1: print(n)종료조건을 설정해준다. 재귀함수는 종료조건 없이는 반복(갔다가 되돌아옴)을 하지 않고 가기만 한다.
문제 2.
nums 는 숫자들이 들어 있는 리스트이다.
nums에 들어 있는 모든 원소들의 합을 리턴하는 재귀함수를 작성하시오.
결과
6
8풀이
def recur_sum(nums:list):앞 문제와 다르게 입력값이 리스트형식이다. 크게 다르지 않지만 리스트 안의 요소에 접근하는 과정에서 한 번 더 생각해야 하는 까다로움이 있다.
if len(nums) == 1: return nums[0]재귀함수의 종료 조건이다.
len(nums) == 0로도 가능하며, 빈 리스트가 입력으로 있을 시 처리가 가능해len(nums) == 0가 좀 일반적인 코드인 것 같다.
else: last = nums[len(nums) - 1] nums = nums[:len(num) - 1] return recur_sum(nums) + last pass한 줄로 아래와 같이 적을 수도 있다.
else: return recur_sum(nums[:len(num)-1]) + nums[len(nums)-1]
last: 리스트의 가장 마지막 요소nums[:len(nums)-1]:nums리스트를 마지막 요소를 하나 뺀 뒤 남은 리스트- 감소된
nums에recur_sum()을 적용해준 뒤 빼뒀던last와 더해준 값을return
문제3
피보나치 수를 리턴하는 함수를 작성하시오.
fibo(n) 함수는 n번째 피보나치 수를 리턴한다.
아래는 피보나치 수열의 점화식이다.
피보나치 수 예시
fibo(0) = 0 # 0번째 피보나치 수
fibo(1) = 1 # 1번째 피보나치 수
fibo(2) = 1 # 2번째 피보나치 수
fibo(3) = 2 # 3번째 피보나치 수
fibo(4) = 3 # 4번째 피보나치 수
fibo(5) = 5 # 5번째 피보나치 수
...결과
0
1
1
2
3
5
8
13
21
34
55풀이
def fibo(n):입력값은 정수
n이다. 피보나치 수열은 첫 두 숫자를 제외한 나머지는 이전, 전전 숫자를 더해서 만들 수 있다. 재귀함수의 '이전의 자기 자신을 통해 구한 수를 현재 값을 구하는 데 사용한다.' 개념과 잘 맞는 문제이다.
if n == 0: return 0 if n == 1: return 1 else: return fibo(n01) + fibo(n-2)피보나치의 0번째 숫자는 0이다. 첫 번째 숫자는 1이다. 나머지는 피보나치 수의 점화식인 f(n) = f(n-1) + f(n-2)로 구할 수 있다.
문제4
입력으로 받은 문자열을 뒤집어서 리턴하는 재귀함수를 작성하시오.
cba
654321풀이
def reverse_str(x):입력값
x: 문자열
reverse_str: 문자열을 거꾸로 출력하는 함수 이름
if len(x) <= 1: return x
x의 길이가 1보다 작거나 같을 때x를 그대로return한다.
만약return와 같이 빈 칸으로 냅두면None이라는 의미로str과 합쳤을 때 타입 에러가 발생할 수 있다.
else: last = x[-1] x = x[:-1] ans = last + reverse_str(x) return ans
last: 문자열의 가장 마지막(오른 쪽)문자
x: 기존 문자열x에서 가장 마지막 문자를 제외한 나머지 문자열
ans:last뒤에reverse_str(x)를 붙여 반복문이 돌아가면서 가장 마지막 문자를 하나씩 더해가며len(x) <= 1이 되었을 때 마지막으로x전체를 붙임으로써 문자열을 뒤집어return할 수 있다.
문제05
파라미터 seq 문자열을 뒤집어서 리턴하는 my_reverse() 함수를 작성하시오.
단, 반드시 재귀적 방법으로 작성하시오.
결과
a
CBA
4321def my_reverse(seq: str) -> str:
pass
# 아래는 수정하지 마시오.
print(my_reverse('a'))
print(my_reverse('ABC'))
print(my_reverse('1234'))문제 04
재귀적 방법을 이용하여 word 가 회문(palindrome)인지를 판별하는 함수를 작성하시오.
결과
True
True
False
True
Falsedef is_palindrome(word: str) -> bool:
if len(word) <= 0:
return True
else:
# 아래는 수정하지 마시오.
print(is_palindrome(''))
print(is_palindrome('a'))
print(is_palindrome('abc'))
print(is_palindrome('aabcbaa'))
print(is_palindrome('aabcbba'))
