13_기초 수학 문제풀이

소인수와 소인수분해

import random
from collections import defaultdict

num = random.randint(100, 1000)
soinsu = defaultdict(int)

prime = 2
print(num)

while num > 1:
    if num % prime == 0:
        soinsu[prime] += 1
        num /= prime
    
    else:
        prime += 1

for key, value in soinsu.items():
    print(key, value)

---

반복문과 재귀함수

반복문과 재귀함수의 관계

• 반복문은 같은 로직을 반복하는 것이고 재귀함수는 자기자신을 다시 호출하는 함수
• 이렇듯 하는 역할이 유사하기 때문에 모든 반복문은 재귀함수로 표현이 가능

반복문과 재귀함수의 차이

• 둘의 가장 큰 차이는 재귀함수의 경우 반복문과 달리 stack overflow를 유발할 수 있다는 데 있음
• 재귀함수는 자기 자신을 계속해서 호출하는 함수이기 때문에 함수가 한번 호출될 때마다 메모리의 stack 영역에 매개변수, 지역변수 등이 저장되게 되고 허용되는 메모리의 크기를 넘어서게 되면 stack overflow가 발생하게 됨
• 또한 기본적으로 반복문이 재귀함수에 비해 더 빠른 실행 속도를 보임

재귀함수의 장점

• 위와 같은 문제점으로 인해 두 방식 모두 표현이 가능하다면 가급적 반복문을 사용하는 것이 좋고, 다음과 같은 경우들에는 재귀함수를 사용하는 것이 좋음
  1. 반복문으로 표현이 어렵고, 재귀함수로 표현하는 것이 흐름에 맞거나 자연스러운 경우
  2. 변수의 사용을 줄이고 싶은 경우: 단순히 적은 변수를 사용한다는 의미 뿐만 아니라 많은 변수 사용으로 인한 예상치 못한 오류를 막아준다는 점에서도 장점이 있음