정글 week01. 핵심 키워드 - 재귀함수와 반복문
팩토리얼로 비교하기
def factorial(n: int) -> int:
if n>0:
return n * factorial(n-1)
else:
return 1#팩토리얼 재귀함수
def factorial(n):
if n==0:
return 1
else:
return n * factorial(n-1)
#팩토리얼 반복문
def factorial2(n):
result =1
for i in range(1, n+1):
result *= i
return result
재귀함수
재귀
어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우
재귀함수와 수학적 귀납법은 비슷하다.예시) 자연수의 정의
1은 자연수이다. 어떤 자연수의 바로 다음 수도 자연수입니다.코드의 간결화 및 변수 사용 최소화 가능하다.
그러나 무한 루프에 빠지지 않기 위해 재귀에서 종료 조건은 코드로 무조건 구현되어야 한다.
재귀 호출(recursive call)
- 직접 재귀
자기 자신의 메서드 내부에서 자기 자신의 메서드 호출 - 간접 재귀
자기 자신의 메서드 내부에서 호출이 아닌 다른 메서드를 통해 자기 자신의 메서드 호출
#직접 재귀 예시
def countdown_direct(n):
if n ==0:
print("it's me hi!")
else:
print(n)
countdown_direct(n-1)
countdown_direct(5)
#간접 재귀 예시
def countdown_even(n):
if n<=0:
print("it's me hi!")
else:
print(n)
countdown_odd(n-1)
def countdown_odd(n):
if n<=0:
print("it's me hi!")
else:
print(n)
countdown_even(n-1)
countdown_even(5)StackOverflow
재귀 호출이 너무 깊어져서 스택 메모리에 더 이상 데이터를 추가할 수 없을 때 발생
재귀 함수는 호출 시마다 스택 공간이 필요
: 스택 메모리에 프레임(Stack Frame)을 추가하고, 해당 재귀 호출이 끝나면 스택에서 제거되지만, 재귀 호출이 너무 많이 중첩되면 스택 메모리가 모두 사용되어 오버플로가 발생한다.파이썬은 이를 방지하기 위해서 콜스택을 1000개만 허용한다.
함수호출이 너무 많을것 같다 싶을때는 반복문을 사용하는 것이 더 좋을 수 있음!
-> stackoverflow를 방지하기 위해 꼬리 재귀를 사용하기도 한다.
꼬리 재귀?
- 재귀 호출이 함수의 반환 직전에 이루어지는 형태
- 재귀 호출이 끝나면 아무것도 하지 않고 리턴하는 방법
- 컴파일러 최적화에 의해 재귀 호출이 깊어져도 스택 프레임이 쌓이지 않고 재사용하기 때문에 빨라진다.
def factorial(n):
if n==0:
return 1
else:
return n*factorial(n-1)
def factorial_tail(n, acc=1):
if n ==0:
return acc
else:
return factorial_tail(n-1, acc*n)factorial_tail(5, 1) -> factorial_tail(4, 5) -> factorial_tail(3, 20) -> factorial_tail(2, 60) -> factorial_tail(1, 120) -> factorial_tail(0, 120) 결과: 120
유클리드 호제법
유클리드 호제법과 재귀를 함께 생각할 수 있다.
:나누어떨어지게 하는 수 중 가장 큰 정수, 최대 공약수 구하기
#반복문
def Euclidean(a,b):
while b!= 0:
[a,b] = [b, a%b]
print(a, b)
return a
#재귀문
def Euclidean2(a,b):
r = b%a
if r ==0 :
return a
return Euclidean2(r,a)재귀함수 분석 방법
- 순수한 재귀 함수: 함수 안에서 재귀 호출을 여러번 실행하는 함수
def recur(n: int) -> int:
"""순수한 재귀 함수 recur의 구현"""
if n > 0:
recur(n - 1)
print(n)
recur(n - 2)
x = int(input('정숫값을 입력하세요.: '))
recur(x)-
하향식
-
상향식
반복문(Loop)
컨테이너 자료형의 여러 원소들에 대해 특정 처리를 할 때 유용하다.
iterable 객체: 반복할 수 있는 객체
파이썬의 대표적인 iterable 객체: list, str, tuplefor 문
for 변수 in 컨테이너: 리스트나 문자열을 순회할 수 있음for name in ["tay", "andrew"]: print(name) --- for character in "hello": print(character)
for i in range(n): 특정 횟수만큼 코드를 반복할 때 사용for i in range(10): print("10번 반복")
- while 문
: 반복 횟수가 정해져 있지 않은 경우
while 조건문:
반복하는 동안 수행되는 동작 1
반복하는 동안 수행되는 동작 2
...조건이 참일 때만 반복문 수행 -> 거짓이 되면 반복 중단
break: 반복문 강제 종료 키워드continue: 다음 반복으로 강제 이동
i = 0
while i < 10:
i +=1
if i % 2 == 0: #i가 짝수이면 다음 루프로 진행
continue
print(i)
if i ==7: #i가 7이면 반복 중단
break
#실행결과
1
3
5
7재귀함수와 반복문 간단 비교.
왜, 언제 쓰는가?
반복문
스택 메모리: 스택 메모리를 사용하지 않음
속도: 빠른 실행
가독성: 코드 길이를 더 길게 만들고 변수가 많아 가독성이 떨어짐
반복문 내부에서 변수의 값이 변경되는 것은 지역 변수의 스코프 내에서 이루어지므로, 추가적인 메모리 관리가 필요하지 않다. 변수는 스택 프레임에 저장되지 않고, 해당 루프의 실행 범위 내에서만 사용되어 메모리를 효율적으로 관리할 수 있다.
재귀함수(Recursion)
스택 메모리: 스택 메모리는 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합을 저장하는데 사용
속도: 느린 실행
가독성: 코드 길이와 변수가 적어 가독성이 높아짐
재귀함수가 반복문보다 느린 이유와 해결 방법?
-> 함수 호출과 복귀를 하기 위한 오버헤드가 발생하기 때문
context switchiing 비용 -> 상대적으로 속도 저하가 발생한다. => 꼬리 재귀 최적화로 해결 가능
240326 추가
피보나치 함수 반복문 vs. 재귀함수
def fibonacci_loop(n):
if n<=0:
return []
elif n ==1:
return [1]
elif n ==2:
return [1, 1]
fibo_seq = [1,1]
for i in range(2, n):
fibo_seq.append(fibo_seq[i-1] + fibo_seq[i-2])
return fibo_seq
def fibonacci(n):
if n<=0:
return []
elif n==1:
return [1]
elif n==2:
return [1,1]
else:
seq = fibonacci(n-1)
seq.append(seq[-1] + seq[-2])
return seq참고)
https://yoondii.tistory.com/134
https://yoon-1212.tistory.com/144
https://namoo-gamedev.tistory.com/35
https://yeonjewon.tistory.com/80
