2022.09.20 화 - 재귀

📄 학습내용

재귀함수

• 재귀(recursive) : 문제를 작은 문제로 나누고 이 작은 문제를 해결을 통해서 문제를 해결하는 방식
• 재귀함수 : 자기 자신을 호출하는 메서드
  • 장점
    • 코드 간결 및 수정 용이
    • 변수 사용 횟수 감소
  • 단점
    • 직관적인 코드 흐름 파악이 어려움
    • proccess stack에 지역변수, 매개변수, 반환값 저장 → 많은 메모리 사용
    • 복귀할 때 컨텍스트 스위치 비용 발생
  • 사용하는 경우
    • 작은 문제로 나눌 수 있는 경우
    • 중첩된 반복문이 많거나 중첩 횟수 예측이 어려운 경우
    • 변경 가능 상태(mutable state)를 제거해서 오류 발생 가능성을 줄이는 경우
  • 모든 재귀 함수 → 반복문 표현 가능

 

재귀함수 작성

1. 재귀함수의 입출력 정의
   • 재귀함수 : 입력 → 출력
2. 기준 설정 및 문제 분해하기
   • 기준 : 입력값이나 문제의 순서와 크기
   • 문제 분해하기
     • 더 이상 분해 가능한 경우와 아닌 경우
3. 재귀의 기초(Base Case)
   • 종료 조건 구현(더 이상 분해되지 않는 경우)
4. 나머지 경우의 수(Recursive Case)
   • 재귀의 기초 이외의 경우의 수 구현
5. 코드 구현

 

객체지향프로그래밍 설계원칙(SOLID)

1. 단일 책임 원칙(SRP, Single Responsibility Principle)
   하나의 모듈은 하나의 책임만을 가진다.
2. 개방 폐쇄 원칙(OCP, Open-Closed Principle)
   확장에 열려 있다 : 프로그램의 동작 추가 및 기능 확장 가능
   변경에 닫혀 있다 : 코드를 수정하지 않고 프로그램의 동작 추가 및 변경 가능
3. 리스코프 치환 원칙(LSP, Liskov Substitution Principle)
   다형성(객체의 하위 타입은 상위 타입으로 대체 가능)
4. 인터페이스 분리 원칙(ISP, Interface Segregation Principle)
   여러 개의 범용 인터페이스보다 하나의 인터페이스 구조가 나음
5. 의존 역전 원칙(DIP, Dependency Inversion Principle)
   추상화에 의존하고 구체화에 의존하지 않는 설계 원칙
   하위 레벨 모듈의 변경이 상위 레벨 모듈의 변경을 요구하지 않음

 

⭐ 공부 난이도

재귀함수 ☆☆★★★

 

🌕 느낀점

  예전에 재귀를 공부했을 때에 이론은 이해가 되었는데 구현이 어려웠다. 어떻게 구현을 해야하는지 모르겠고 할 때마다 고민을 해도 잘 모르겠다는 생각이 들었다. 지금 재귀를 하루종일 공부를 해보니까 왜 구현이 어려웠는지 알 것 같다. 재귀의 이론만 알고 어떻게 구현할지에 대해서 고민을 제대로 해보지 않았던 것 같다. 이번에 예제를 직접 작성해보고, 관련 문제를 계속 풀어서 이제는 어떻게 해야할지 감이 잡힌다. 깊이우선탐색이나 너비우선탐색을 아무리 풀어도 제대로 풀지 못했던 이유가 재귀에 대한 개념이 제대로 안 잡혀 있어서 그런 것 같다. 기초가 정말 중요하다고 다시금 깨닫는다.