재귀함수란?
- 함수가 함수를 또 호출할 수 있는 것
- 재귀적 호출 : 함수가 본인을 호출하는 것
팩토리얼 함수
재귀함수의 대표적인 사례인 팩토리얼을 보자.
def factorial(n):
if n == 1: # 베이스 케이스
return 1
else: # 재귀 케이스
return factorial(n-1) * n
print(factorial(4))5! = 4!*5
여기에서 4!이 5!의 하위문제다.
이렇게 쭉 내려가다가
1! 까지 가면 하위문제가 없다.
4!, 5! 처럼 하위문제가 있는 건 재귀 케이스
1! 처럼 답을 바로 알 수 있는 건 베이스 케이스 라고 한다.
재귀문제 푸는 법
1) 하위문제 찾기
- 어떻게 재귀적으로 접근할지를 결정
- 파라미터로 받은 input의 사이즈를 1 줄였을 때 어떤 게 리턴될까? 를 생각하면 좋음
2) 재귀케이스, 베이스 케이스 정함
- 재귀 케이스 : 하위문제가 있는 경우
- 베이스 케이스 : 하위문제 없이 바로 정답을 아는 경우로 설정
3) 함수구현
위 순서를 기억하고 리스트 요소를 뒤집는 함수를 구현해보자
[1, 2, 3, 4,] > [4, 3, 2, 1]
def revers(my_list):
# 베이스 케이스
if len(my_list) <= 1:
return my_list
# if문에 안 걸리면 위는 실행 안 되니 else문 없이도 가능!
return my_list[-1:] + reverse(my_list[:-1])
print(reverse([5,4,3,2,1]))스택 오버플로우
위의 예시 코드를 보면 모두 반복문으로 작성할 수 있다.
따라서 재귀함수, 반복문함수는 모두 서로 바꿔서 구현할 수 있다.
재귀함수를 구현할 때 주의해야 할 점이 스택 오버플로우이다.
함수를 호출할 때 호출된 위치를 기억하기 위해 컴퓨터 메모리 안의 ‘콜스택’이라는 곳에 저장해둔다.
재귀적으로 함수를 호출하면, 함수가 끝나지 않은채로 콜스택에 계속 쌓이게 되고, 콜스택의 공간이 부족해져서 발생하는 오류를 스택 오버플로우라고 한다.
파이썬은 이 오류를 피하기 위해 쌓여있는 함수를 1000개 미만으로 설정해뒀다.
그래서 factorial(2000)을 호출하면, Recursion Error가 발생한다.
그럼에도 불구하고 재귀함수를 썼을 때 코드를 훨씬 자연스럽고 깔끔할 때가 있어서 알고 있는 게 좋다!
예제) 백준 10994번 : 별 찍기 - 19
문제 및 예제
문제 파이썬 풀이
def star(x):
if x == 1:
st = '*'
else:
first_cnt = 4*(x-1)+1
st = str('*'*first_cnt + '\n' +
'*' + ' '*(first_cnt-2) + '*' + '\n' +
'\n'.join(['* '+x+' *' for x in str(star(x-1)).split('\n')]) + '\n' +
'*' + ' '*(first_cnt-2) + '*' + '\n' +
'*'*first_cnt)
return st문제는 런타임 에러가 뜬다는 것.... 해결할 방법 아시는 분은 연락주시와요
