🌈 [Section2] 1. 재귀함수

📕 오늘 배운 내용!

• 재귀함수

---

✏️ 재귀함수 (Recursion)

• 함수 내에서 자기 자신을 다시 호출하는 것
  ➜ 자기자신을 계속 다시 호출하다보니 반복이 됨

• recursion() 메서드 호출하면 첫 실행문이 다시 호출되어 계속 반복

• 모든 재귀함수는 반복문(for/while문)으로 쓸 수 있음

• Base case : 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  ( 문제를 더이상 쪼갤 수 없는 경우 )

• Recursive case : 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 함수
  (자기 자신을 계속 반복 호출 하여 문제를 작게 쪼개나가는 코드)

but, 메모리도 너무 많이 사용하고 코드의 흐름을 예측하기 너무 힘들기 때문에 서비스 로직을 사용할 경우에는 잘 안씀 (나중에 배울 문법을 위해 배우는 것)

---

Ex. num을 매개변수로 가진 sum이라는 메서드가 있고, 1부터 num까지의 합계를 구해야 할 경우에

static int sum (int num) { //1부터 num에 들어갈 숫자까지의 합계를 구할건데
	if (num == 1) return 1; //Base case //만약 num이 1이면 1리턴하고
    else return num + sum(num - 1);
    //Recursive case
    //아닐 경우 Sum 의 첫번째 요소 + 첫 요소 제거하고 Sum 의 나머지 요소가 담긴 것
} 

⬆️ 위 식에서 만약 num = 5 라고 한다면,

메서드 안에 조건식이 없을 경우 그냥 sum(5) 대입하고 num을 출력한다면 원래는 그냥 5가 출력됨

하지만 밑에 조건식을 보면 else 부분에 sum(5)일 경우 ➜ 5 + sum(4) 를 불러오래

여기서 sum(4)는 다시 저 식의 num에 4를 대입한 것과 같기 때문에 4 + sum(3)이 됨

이렇게 3 + sum(2) / 2 + sum(1) 로 점점 쪼개지다가 num이 1이 되면

위에 if문에서 이 식을 멈추기 위해 조건으로 1을 리턴하라고 되어있음
➜ else 조건식 건너뛰고 1 반환

➜ 결국은 쭉 자기자신들이 더해져 5 + 4 + 3 + 2 + 1 이 되는 것

---

✔ 재귀함수 장점

• 코드가 간결

• 수정이 용이

• 변수 여러개 사용할 필요 X

✔ 재귀함수 단점

• 코드의 흐름 바로로 파악하기 어려움

• 반복적으로 매서드를 호출하면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 되는데 이 과정이 반복문에 비해 메모리를 더 많이 사용

• 메서드 호출, 매서드 종료 이후에 다시 자기자신 복귀를 위한 컨텍스트 스위칭 비용이 발생

✔ 재귀함수 사용 조건

• 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야함

• 재귀 호출이 종료되는 시점이 존재해야 함

✔ 사용이 적합한 경우

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

• 반복문의 중첩 횟수(number of loops)가 많거나 예측하기 어려운 경우

• 변수 사용을 줄여 오류 가능성을 줄일 경우

• 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

---

🌈 느낀점

오늘 재귀함수는 사실 처음에 봤을 때는 머리로는 '자기 자신을 불러온다' 라는 개념을 이해를 했지만 막상 코드를 보니 '저 코드가 왜 자기 자신을 다시 불러오는 거지..?' 하는 점이 계속 이해가 가지 않았다.
그래서 예시로 5라는 수를 대입하여 어떻게 돌아가는 건지 구조를 하나하나 생각해보았는데,
처음엔 이것도 이해가 안돼서 못하다가 식 안에 '함수명(숫자)' 이렇게 적는 부분이 자기 자신으로 다시 돌아가 그 식 안에 다시 대입을 하여 점점 쪼개지는 것이라는 구조가 이해가 되었다!!
이 구조를 이해하다보니 페어와 푸는 문제에서도 적용을 하였고 내가 이해한 점을 다시 페어에게 설명하며 같이 풀 수 있었다.
물론 아직까지 완전히 이해를 한 것 같진 않지만 더 공부해야겠다 🌈 ☘️