재귀함수(Recursion), 반복문(Iteration)

재귀함수(순환함수,Recursion)

함수 내에서 자기 자신을 호출하는 함수 => 알고리즘을 설계할 때 동일한 작업의 조금 더 작은 경우를 재호출하여 사용 (스택 메모리 사용)

재귀함수 예(마트료시카)

 

 

장점 :

- 중복된 코드를 제거함으로써 프로그램의 간결화

 

단점 :

- 코드 중복 제거로 인한 이해가 어려워지고, 메모리를 많이 차지

- 반복문으로 변환된 프로그램의 수행 속도가 순환으로 구현된 프로그램보다 항상 빠르다는 보장 X 

 

재귀 함수의 조건 :

1.  반드시 종료가 되는 조건이 존재 ◁ 조건을 설정 안할시 무한반복(단 횟수는 1024bit 까지 제한)

2.  계산의 범위가 점점 줄어져야 한다.

 

종료 시점이 없을 경우의 재귀함수

 

재귀 호출의 작동 :

- 상자를 반복해서 여는 과정을 재귀 호출 형태로 표현

 

재귀함수의 원리

#재귀함수의 예)

def openBox() :
	print("재귀함수의 무한 반복")
    openBox()
    
openBox() # 처음 함수를 다시 호출 (무한 반복)

---

순환과 반복

---

• 순환(recursion)

- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법

- 함수 호출의 오버헤드가 있음

- 대부분의 순환은 반복으로 바꾸어 작성할 수 있음 단, 팩토리얼 문제의 경우 순환과 반복 알고리즘의 시간 복잡도는 O(n)으로 동일

- 간결한 코딩 가능

대표 : 팩토리얼, 피보나치 수열, 이항 계수, 이진 탐색등 

 

 

반복이 아닌 순환을 쓰는경우?)

- 정의자체가 순환적으로 되어 있는 문제나 자료구조일 경우

 

순환이 적합한 경우(대표)

- 그외) : 이항계수, 하노이의탑, 이진 탐색, 이진트리  등 

 

• 순환 호출의 장점

- 중복된 코드를 제거함으로써 프로그램이 간결화가 가능!

 

• 순환 호출의 단점

- 코드 중복 제거로 인한 이해가 어려워지고, 메모리를 많이 차지

 

- 반복문으로 변환된 프로그램의 수행 속도가 순환으로 구현된 프로그램보다 항상 빠르다는 보장 X 

 

 

 

순환 호출의 비효율성

- 같은 항이 중복해서 계산이됨

- 예를 들어 fib(6)을 호출하게 되면 fib(2)가 4번이나 중복되어서 계산이 됨(성능저하, 메모리 낭비)

- 이러한 현상은 n이 커지면 더 심각해진다.

 

순환 호출을 사용했을 경우의 비효율성

---

• 반복문(Iteration)

- 어떤 작업을 여러 번 반복해서 수행하고 싶을 때 사용하는 제어 구조

- 복잡하고 지루한 반복 작업을 자동화하고 코드의 간결함을 유지하는 데 필수적인 도구

- 보통 수행속도가 빠름

- 문제에 따라 프로그램 작성이 어려울 수 있음

 

종류 :

 

1. for 반복문

 

• 정해진 횟수만큼 반복할 때 사용
• 일반적으로 반복 횟수가 명확할 때 적합

예시)

 

for i in range(5):
    print(f"{i}번째 반복입니다.")
    
#결과 : range(5)는 0부터 4까지 총 5번 반복

 

2. while 반복문

 

• "조건이 참(True)"인 동안 계속해서 반복.
• 조건을 기반으로 반복할 때 사용됩니다.

i = 0
while i < 5:
    print(f"{i}번째 반복입니다.")
    i += 1

"""조건이 만족하지 않으면 반복을 멈춤
무한 루프에 빠지지 않도록 조건이 언젠가는 거짓이 되도록 작성해야 함!"""

 

 

 

3. do-while 반복문 (Python에는 없음)

 

• 조건을 나중에 검사하는 반복문
• 반드시 한 번은 실행된다는 점이 특징
• Java, C, C++ 등 일부 언어에서 지원

int i = 0;
do {
    System.out.println(i + "번째 반복입니다.");
    i++;
} while (i < 5);

 

 

반복문의 제어구문

 

🔹 break

 

- 반복문을 즉시 종료

for i in range(10):
    if i == 5:
        break
    print(i)

 

🔹 continue

 

- 해당 반복을 건너뛰고 다음 반복 진행.

 

for i in range(5):
    if i == 2:
        continue
    print(i)

 

반복문과 알고리즘

반복문은 다양한 알고리즘의 기본 요소가 됨,

 

예를 들어:

• 리스트 탐색
• 누적 합 구하기
• 정렬 알고리즘 구현
• 피보나치 수열 계산

등 대부분의 문제 해결에 반복문은 빠질 수 없습니다.

 

 

반복문 사용 시 주의할 점!

 

1. 무한 루프 주의

- 조건이 영원히 참이라면 프로그램이 중단 X

while True:
    print("끝나지 않는 반복~~")

 

 

2. 복잡한 중첩은 피하기

- 반복문 안에 반복문을 또 넣는 중첩 루프는 경우에 따라 성능 문제를 유발할 수 있음

 

3. 조건 확인 철저히

- 예상치 못한 결과가 나오지 않도록 조건문을 꼼꼼히 점검할것!

 

 

 

번외) 일반적인 무한 루프 멈추는 단축키!

 

사용환경	멈추는 방법	설명
터미널 (Windows, Mac, Linux)	Ctrl + C	가장 보편적인 종료 방법. 루프 강제 종료.
파이썬 IDLE	Ctrl + C 또는 강제 종료	IDLE에서 직접 멈추는 건 어려울 수 있어서 창을 닫거나 강제 종료 필요.
VSCode / IntelliJ 터미널	Ctrl + C	내장 터미널에서도 작동함.
Jupyter Notebook	⏹️ (정지 버튼) 클릭	또는 메뉴 > Kernel > Interrupt Kernel
웹 브라우저에서 실행 중인 JavaScript 루프	탭 닫기 / 브라우저 강제 종료	무한 루프는 브라우저 멈춤 현상 유발 가능.
Eclipse, NetBeans 등	콘솔 창에 있는 "Terminate" 버튼	강제 종료 가능.

---

반복문 vs 재귀함수

항목	반복문	재귀함수
개념	조건을 만족할 때까지 블록을 반복실행	함수가 자기 자신을 호출하여 반복
종료조건	반복문 내부에서 조건식으로 판단	보동 if문으로 "종료조건"을 명시
메모리 사용	적은 메모리 사용 (일반적인 변수만 사용)	함수 호출시 스택에 쌓여 (프레임 누적) 메모리 사용이 큼
성능	효율적	성능 저하나 스택 오버플로우 발생 가능
가독성	간단한 반복에 유리	수학적 문제나 트리 탐색 등 논리적인 표현에 유리
사용 예시	리스트 순회, 단순 반복 작업	팩토리얼, 피보나치, 트리/그래프 탐색
디버깅 용이성	쉬움	다소 복잡

---

요약 :

재귀함수는 함수 내에서 자기 자신을 호출하는 함수

장점 : 중복된 코드 제거로 인한 프로그램 간결화

단점 : 코드를 이해하기 어려워지고 메모리를 많이 차지

조건 : 반드시 종료가 되는 조건과 다음 호출 시 계산의 범위(규모)가 점점 줄어야 한다는 조건을 성립