2022-05-[24~25](Section2_Algorithm_재귀)

0. 시작하게 된 계기 및 다짐 😮

• 이번 코드스테이츠의 백엔드 엔지니어링 개발자 부트캠프에 참여하게 되면서 현직개발자 분들의 빠른 성장을 위한 조언 중 자신만의 블로그를 이용하여 배운 것 들을 정리하는게 많은 도움이 된다 하여 시작하게 되었다.

  • 그 날 배웠던 것을 길지 않아도 좋으니 정리하며 복습하는 습관 기르기
  • 주말에 다음주에 배울 내용들을 예습
  • 코딩 문제와 java코드들은 꾸준히 학습
  • Spring framework과 서버/클라이언트/DB 공부

1. 학습 목표 😮

목표	결과
문제를 잘게 쪼개어 해결하는 사고	O
반복적으로 함수를 호출 방식	O
반복문의 중첩 횟수를 예측이 어려울 때	O
변수 사용을 줄이고 문제의 구조를 작게	O

2. 정리

재귀적 문제 풀이 방식

1. 재귀 함수의 입력값과 출력값 정의
 - arrSum: [int] -> int
2. 문제를 쪼개고 경우의 수를 나누기
 - arrSum(new int[]{1, 2, 3, 4}) = arrSum(new int[]{2, 3, 4])  풀이방식 같음
3. 쪼개어진 단순한 문제 해결
 - arrSum: [number] => arrSum(new int[]{}) = 0
4. 복잡한 나머지 경우 해결
 - arrSum: [number] => arrSum(new int[]{e1} + arrSum(new int[]{e2, ..., en]}

public int arrSum(int[] arr){
    if(arr.length() == 0) return 0;
    return arr[0] + arrSum(arr.copyOfRange(1,arr.length()));
}

# 피보나치 메모이제이션 참조

재귀함수와 메모리 사용량 간의 관계

 - 실행 중인 함수의 실행 절차에 대한 정보는 실행 컨텍스트(함수의 세부정보/제어흐름등 현재위치,변수의 현재값등의 상세 내부정보)에 저장됨
 - 재귀함수는 반복적 함수 호출로 메모리를 많이 사용하여 이 실행 컨텍스트를 계속 저장하기에 메모리를 차지해 스택 오버플로우를 일으킬 수 있다.
 - but, 알고리즘 자체가 재귀적으로 표현하는게 가독성이 좋거나 변수 사용량을 줄여줄 수 있기 때문에 필요에 경우에 사용한다.
 
 꼬리재귀
 - 재귀함수의 단점을 보안하기 위한 방법이다.
 - 재귀호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 사용 형태
 - 컴파일러가 선형으로 처리하도록 알고리즘을 변경하여 스택을 재사용하게 한는 방식이다.(단, 컴파일러가 이 기능을 지원해야 가능)

---

ex) 

일반재귀 Code

 function func(n) {
   if(n == 1 ){
       return 1;
   }
   return n*fac(n-1);          
==> 재귀 호출로 인한 함수로 추가적인 연산이 필요하여 스택에 이 값들을 저장해 두어야 한다.

꼬리 재귀 Code
 
 fuction func(n,total=1){
   if(n==1){
     return total;
   }
  return func(n-1,n*total);  
==> 재귀 호출로 인한 함수로 추가적인 연산이 필요없기 때문에 스택을 덮어쓰는 방식으로 하는 꼬리재귀


---
extra).

하노이의 탑 재귀(java tower of hanoi in recursion) 
 - 재귀를 활용한 대표적인 문제

조합 재귀 함수(java combination in recursion)
 - 알고리즘에서 자주 사용되는 조합 재귀 함수

★ 실습_StringfiJSON 구현(Git)

3. 피드백 😮

• 알고리즘을 해결하기 위한 방법 중 재귀에 대하여 살펴 보았다.

• 이는 반복문을 변수에 따라 다르게 사용하거나 반복문의 개수를 파악하기 힘들 때 사용하면 굉장히 유용하게 알고리즘 문제를 해결할 수 있지만, 반복해서 함수를 호출하기에 메모리 이슈가 있지만 메모리가 많이 늘었고 꼬리재귀등 의 방법을 이용하여 많이 해결 할 수 있다.

4. 앞으로 해야 될 것 😮

• 매일 꾸준히 할 것
  • 꾸준히 velog 작성
  • Java 언어 및 Algorithm 공부(Coding-Test)
  • 틈틈히 운동 하기

---

• 내일 해야 할 것
  • 알고리즘_자료 구조중 Stack/Queue등 많이 사용하는 자료구조 형식 공부
  • 이들을 실제로 활용하여 알고리즘 문제 해결(코플릿)