코드잇 알고리즘 강의!
재귀함수
: 자기 자신을 호출하는 함수
재귀적으로 문제를 푼다는 것 = 같은 형태의 더 작은 문제를 풀고, 부분 문제의 답을 이용해서 기존 문제를 푸는 것
재귀함수 문제는 경우를 나눠서 풀어야 한다.
- Base Case : 문제가 충분히 작아 바로 풀 수 있는 경우
- Recursive Case : 재귀적으로 부분문제를 푸는 경우
def factorial(n):
if n == 0: # base case 구현
return 1
return factorical(n-1) * n # recursive case 구현
print(factorial(5))재귀 함수 문제는 반복문으로도 풀 수 있다
재귀함수 단점
- 호출이 너무 많으면 Call stack이 쌓여 공간이 부족해 과부하로 StackOverFlowError 발생
- 따라서 너무 큰 파라미터를 넘기면 에러 발생
- ex ) factorial(2000)
- 콜스택이 너무 많이 쌓일 것 같으면 반복문으로 푸는 것이 더 효율적
자릿수 합 예시
: 파라미터로 정수값 n을 받고, n의 각 자릿수의 합을 리턴해주는 재귀함수 sum_digits를 작성하라.
- 인풋 n이 어떤 특징을 가질 때 base case 일까?
- n이 한 자릿수면, 구할 것 없이 n을 리턴해주면 된다.
- 그렇다면 recursive case는 무엇일까?
- n이 한 자릿수 이상일 때다.
def sum_digits(n):
if n < 10:
return n
return n % 10 + sum_digits(n // 10)재귀함수 문제
- 백준 10870번
- 백준 11729번
- 백준 9095번
