[WEEK01] 반복문과 재귀 함수

반복문

반복문은 특정 조건이 충족될 때까지 코드 블록을 반복 실행하는 구조다. 파이썬에서는 for와 while 두 가지 반복문을 제공한다. for문은 정해진만큼 돌리고, while문은 어떤 목표까지 돌린다.

for 문

for 문은 주어진 시퀀스(리스트, 문자열 등)의 각 요소에 대해 반복한다.

fruits = ['apple', 'banana', 'kiwi']
for fruit in fruits:
    print(fruit)
    
# 1부터 10까지 출력
for i in range (1, 11):
    print(i)

while 문

while 문은 주어진 조건이 참인 동안 계속해서 반복한다.

# 1부터 5까지 출력
count = 1
while count <= 5:
    print(count)
    count += 1

 

while 문의 조건을 1이나 True로 설정할 경우 무한반복문을 만들 수 있다. 단, 언제 무한반복이 끝나는지 설정하는 코드를 추가해줘야 한다.

i = 0
while True:
  i += 1
  print(i)
  if i > 500:
    break

 

반복문의 장단점은 다음과 같다.

• 장점 : 코드가 간결하고 이해하기 쉽다. 일반적으로 성능이 좋다.
• 단점 : 반복 횟수가 미리 정해져 있지 않거나 복잡한 경우 코드가 복잡해질 수 있다.

---

재귀함수

재귀함수는 자기 자신을 호출하는 함수다. 문제를 더 작은 부분으로 나누어 해결하는 방식으로, 주로 분할 정복 알고리즘에서 사용된다.

 

재귀 함수의 구조는 다음과 같다.

• 기저 사례 : 재귀 호출이 더 이상 필요하지 않을 때의 조건
• 재귀 호출 : 문제를 더 작은 문제로 나누어 자기 자신을 호출하는 부분

재귀함수의 장단점은 다음과 같다.

• 장점
  • 코드가 간결하고 이해하기 쉽다. 복잡한 문제를 단순화할 수 있다.
  • 트리 구조와 같은 문제를 해결하는 데 유용하다.
• 단점
  • 호출 스택이 쌓이므로 메모리 사용량이 많아질 수 있다
  • 큰 입력값에 대해 스택 오버플로우가 발생할 수 있다.
  • 반복문에 비해 성능이 떨어질 수 있다.

파이썬은 최대 재귀 한도를 정해 허용되는 재귀 호출의 최대 반복 횟수를 지정한다. 다음 코드는 사용하는 파이썬 버전에서 설정된 최대 재귀 한도를 확인하는 코드이다.

import sys
print(sys.getrecursionlimit())

팩토리얼

팩토리얼 구현은 재귀 함수를 사용하는 대표적인 예시이다.

import sys

def facto(n):
    if n <= 0: return 1
    else: return n * facto(n-1)

n = int(sys.stdin.readline())
print(facto(n))

이 코드에서는 if n <= 0: 구문이 기저 사례, else: 구문이 재귀 호출에 해당한다.

하노이 탑

하노이 탑 문제도 재귀 함수를 사용하는 또 다른 예시이다.

def hanoi(n, s, e):
    m = 6 - s - e
    if n > 1: hanoi(n-1, s, m)
    print(s, e)
    if n > 1: hanoi(n-1, m, e)

n = int(input())
print(2**n - 1)
if n <= 20:
    hanoi(n, 1, 3)

8퀸 문제

[백준] (9663) N-Queen