[알고리즘] 재귀함수 | 재귀 문제를 풀 때의 접근법...

드디어 재귀함수 복습 시간이 왔다!!!

 

휴학하고 알고리즘 개념을 까맣게 잊어버리면서 살았더니

재귀에 대한 두려움이 생긴 것 같다...

 

다시 열심히 복습해보자!!!

 

---

 

 

재귀 함수

함수가 자기 자신을 호출하여 문제를 반복적으로 해결하는 기법

주로 문제를 작은 단위로 나누고, 반복적으로 처리해야 할 때 사용!

 

기본 구조 및 특징

베이스 조건(Base Case)
재귀 호출을 멈출 조건.  문제를 더 이상 나누지 않고 결과를 반환한다.

 

재귀 호출(Recursive Call)
함수가 자기 자신을 호출하여 문제를 작게 나눈다.

 

 

 

 

특징

함수 호출이 스택 구조로 쌓인다. 따라서 호출이 많아지면 Stack Overflow가 발생할 수 있다

 

def factorial(n):
    if n == 0 or n == 1: # 기저 조건
        return 1
    return n * factorial(n - 1) # 재귀 호출

print(factorial(5))  # 결과: 120

 

 

여기까지는 이미 알고있던 내용이다.

 

---

 

* 참고: https://velog.io/@eddy_song/you-can-solve-recursion

 

재귀 함수의 개념을 알아도 어떻게 문제를 풀어야하는지 감이 오지 않았는데,

해당 블로그를 읽고 재귀 문제 접근 방법에 감을 잡을 수 있게 되었다!

(잘 정리해주셔서 너무 감사드립니다... 👍😭)

 

재귀 함수 문제를 해결하는 접근법

"재귀적으로 생각하지 말자"

- 머릿속에서 함수 실행 순서를 그리려고 하지 말자

- 처음부터 큰그림을 그리지 말고, 중요한 부분들에만 초점을 잡고 좁혀서 문제를 풀어나가자

 

4가지 접근 방법

---

1단계. 재귀를 꼭 써야 하는가?

2단계. 베이스 조건: 답을 바로 알 수 있는 가장 간단한 상황을 생각한다.

3단계. 분해: 베이스 조건에 가까워지도록 인풋값을 조작한다.

4단계. 조합: 부분 답을 가지고 전체 답을 구하는 방법을 생각해본다.

---

 

1단계. 재귀를 꼭 써야 하는가?

반복문 대신 재귀를 꼭 써야만 하는 이유를 생각해봐라.

일반적으로 반복문이 재귀보다 낫다. 재귀는 스택에 정보가 쌓여 메모리를 많이 차지한다.

 

(1) 재귀적인 자료구조나 풀이 공식이 있을 때

(2) 변수 선언 없이 코딩하고 싶을 때

 

주로 사용된다

 

 

 

2단계. 베이스 조건

답을 바로 알 수 있는 가장 간단한 상황을 생각한다.

더 이상 자기 자신을 호출하지 않게 하는 조건!

 

"바로 답을 구할 수 있는, 가장 단순한 인풋값이 무엇일까?"

 

재귀적으로 복잡하게 생각하지말자!!! 1차원 문제인 것처럼 풀자.

 

 

3단계. 분해

재귀 함수가 잘 작동하려면, 함수를 호출할 때마다 베이스 조건에 가까워져야 한다.

베이스 조건에 가까워지도록 인풋값을 조작하자.

 

 

분해의 흔한 패턴

• 정수 타입이라면 대체로 n - 1 혹은 n - 2.
• 배열이라면 앞의 숫자 하나를 떼고 길이를 줄인다. [1,2,3,4] → [2,3,4] → [3,4] 이런 식으로. 문자열도 마찬가지.
• 링크드 리스트라면, 포인터가 가리키는 다음 노드, 혹은 다다음 노드를 넣는다.
• 트리라면, 자식 노드를 하나씩 넣는다. (이진 트리의 경우 재귀 호출을 2번 하는 경우가 많다.)

 

4단계. 조합

재귀 호출이 베이스 조건에 걸려 멈추고 나서,

거기서부터 감았던 실타래가 풀리듯이 결과값들이 차례차례 반환되는 것을 조합이라고 한다.

 

복잡하게 생각할 것 없이

 

재귀 과정 전체의 조합을 생각하지 말고, 특정한 단계를 딱 어서 보자.
그 단계에서 바로 밑의 재귀 호출로 얻은 답을 가지고, 현재 단계의 답을 어떻게 낼 것인가? 를 생각하면 된다!

 

베이스 조건 바로 윗단계, 베이스 조건 3단계 위의 상황을 가정하고 둘의 규칙성을 찾는다.

이 2단계에서 제대로 답이 나온다면, 거의 모든 경우에 재귀는 자연스럽게 답으로 가게 되어있다

 

 

 

오케이!!! 파이팅. 문제 잘 풀어보자!!!!