[Section2] 01. 자료구조와 알고리즘 기초 - 재귀

🧑🏻‍💻 TIL(Today I Learned)

---

✔️ 재귀 함수 

 

재귀 함수란? 

➡️ 재귀함수는 함수(메서드) 내부에서 자신을 호출하여 실행하는 함수(메서드)

📍 재귀(Recursion)란?
: 한 문제를 동일한 구조의 작은 문제로 나눌 수 있고 작은 문제를 해결함으로써 전체 문제를 해결하는 방법  

public void recursion() {
  System.out.println("This is");
  System.out.println("recursion!");
  recursion();
}

• 장점 
  • 불필요하게 여러 개의 반복문을 사용하지 않기 때문에 코드가 간결해지고 수정이 용이함
  • 변수를 여러 개 사용할 필요가 없음
• 단점
  • 반복문과 달리 코드의 흐름을 직관적으로 파악하기 어려움
  • 반복하여 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장함 이러한 과정은 반복문에 비해 메모리를 더 많이 사용하게 됨
  • 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용 발생 
    : 재귀 함수는 자기 자신을 호출하면서 새로운 스택 프레임을 계속 생성하고 이렇게 계속해서 스택 프레임을 생성하고 제거하는 작업은 컨텍스트 스위칭 발생시킴

컨텍스트 스위칭(context switching)
→ 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해 이전의 프로세스의 상태를 보관(PCB, Process Control/Context Block)하고 새로운 프로세스 상태를 적재하는 작업

 

🔎 재귀 함수를 사용하기 위한 조건

• 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 함 
• 재귀 호출이 종료되는 시점이 존재해야 함 

 

🔎 재귀가 적합한 상황

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 경우
2. 중첩된 반복문이 많거나 반복문의 중첩횟수(number of loops) 예측하기 어려운 경우
3. 변수 사용을 줄여 mutable state(변경 가능한 상태) 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우 

 

---

Section2 가 시작되었다. 분명 유어 클래스를 볼 때는 이해한 것 같았는데 막상 코플릿 문제를 풀려니까 갑자기 혼란스러워져서 몇 문제 풀지도 않았는데 끙끙 거렸다. 페어 분이 아니였다면 진짜 하루 종일 머리카락 쥐어뜯고 있었을 듯...... 또 얼른 코플릿 문제 마저 풀러 가야지......