재귀함수
재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.
내부적으로 반복하다, 일정한조건을 만족하면 함수를 이탈하여 결과를 도출한다.
문제 풀이에서 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되므로 잘 알아야 하고 쉽게 벽을 느낄수 있다.
재귀의특성
- 재귀는 같은 일을 하는 함수끼리 상태만 달리하여 호출한다.
- 무슨 일을 했는지는 중요하지 않다.
- 재귀호출이 무한히 발생할수 있다. (점화식)
def recursive():
print("이것은 재귀함수입니다.")
recursive()
recursive() #함수 호출
이렇게 되면 무한히 출력된다.
def recursive(count):
if count == 0:
return
print("이것은 재귀함수입니다.")
count -= 1
recursive(count)
recursive(5) 실행
이렇게 코드를 쓰면 5번 출력하고 코드가 종료된다.
재귀 함수를 이용해 작성할 수 있는 몇가지 함수에 대해 알아보겠다.
1) 팩토리얼 함수
팩토리얼은 !를 기호로 사용하고 n부터 1까지 곱한 값을 구할때 사용한다
3! = 3*2*1
팩토리얼 함수는 반복분, 재귀함수 모두로 구할 수 있다.
반복문 사용
def factorial(n):
res = 1
for i in range(1, n+1):
res *= i
return res
# 재귀함수 사용 팩토리얼
def factorial(n):
if n=1: # n이 1 일때
return 1 # 1 리턴후 재귀호출 끝
return n * factorial(n-1)
2) 피보나치 수열
피보나치 수열 f(n) = f(n-2)+f(n-1) 라는 식을 가졌다
def fib(n):
a,b = 1,1
if n==1 or n==2:
return 1
for i in range(1,n):
a,b = b, a+b
return a
이렇게 이해를 잘 했다고 하고
https://www.acmicpc.net/problem/17478 이 문제를 풀면 나처럼 왜 이런식으로 나오지? 라고 생각하는 사람이 있을 것 같다.
그 이유는 재귀함수의 흐름에 대해 잘 이해해야 한다.
재귀함수의 흐름이다.
즉 7번에는 "____라고 답변하였지1." 9번에 "라고 답변하였지1" 가 출력된다.
재귀함수의 장단점
장점 : 변수를 여러개 만들 필요가 없다. 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일수 있다.
코드가 간결해진다.
단점: - 지속적으로 함수를 호출하기때문에 변수,반환값을 process stack 에 저장해야한다 . 메모리 사용이 반복문에 비해 크고
이는 속도저하로 이어진다.
- 복귀를 위한 컨텍스트 스위칭에 비용이 발생한다.
cf) stack 이란 후입선출인 자료구조이다
참고:https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60
https://seongonion.tistory.com/24
댓글