[CS]재귀(Recursion)

강동현·2023년 12월 22일

CS

목록 보기

1/19

1. 재귀에 대한 고찰

[필독]재귀 함수를 해석할 때 함수를 절대로 따라들어가지 마라
따라들어간 순간 어느새 늪에 빠져있는 나 자신을 발견하게 된다.

수학시간마다 점화식(수학적 귀납법)이 나올 때마다, 뭔소린가 싶었다.

프로그래밍에서 재귀가 나올 때, 본능적으로 점화식 = 재귀라는 것을 느꼈다.

교수님 says, "처음이 되면 -> 끝까지 된다.(때문에 믿자)"라고 하셨다.

이런 작은 TIP을 가지고 재귀를 파해쳐보자

수학 문제를 풀듯 풀어야 한다 = 점화식을 만들어야 한다.

실제 수학 문제를 풀듯 노트와 펜을 꺼내 점화식을 만드는 과정 필요

기존 코딩 방식인 뇌 내 사고론 풀기 어렵다는 것이 함정

2. 재귀란?

재귀: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
void func(int n){
	if(n == 0) return;
    cout << n << ' ';
    func(n-1);

3. 재귀 조건

재귀 함수에 반드시 존재해야 하는 것
재귀 함수를 잘 짜기 위해 명확히 설정해야 하는 것

재귀 조건1 = 종료 조건(Base Condition = Base Case)
특정 입력에 대해 재귀가 탈출할 종료 조건(Base Condition)이 있어야 함
모든 입력은 이런 종료 조건으로 수렴(도달)해야 함

재귀 조건2 = 점화식(수학적 귀납법)
k 단계에서 성립하면 k+1 단계에도 성립해야 함

재귀를 정의할 때, 명확히 설정할 것들
1. 함수의 정의: 함수의 역할과 인자 설정
2. Base Condition: 어디까지 계산한 후 자기에게 넘겨줄지
3. 재귀 식(점화 식)

4. 재귀 정보

모든 재귀는 반복문으로 구현 가능하다.

함수 호출의 비용이 크므로, 반복문으로 구현 가능하면, 굳이 재귀로 짤 필요가 없다.

장점: 코드의 간결성 및 가독성
재귀 없이 구현하려면, 코드가 너무 복잡한 경우, 사용

단점: 비효율적이다.
함수 호출의 비용이 크기 때문에, 메모리/시간상의 손해를 봄
시간 복잡도: $O(2^n)$ -> $O(n)$ [DP 활용 시 개선 가능]

5. 귀납적 사고

함수를 작성한 후, 절차 지향적이 아닌 귀납적 사고로 함수를 확인해야 한다.
"절대 함수를 따라 들어가면 안된다."

n = 기본 값일 때, 잘 동작함을 확인

n = k일 때 잘 동작한다 가정했을 때, n = k + 1일 때 잘 동작함을 확인하면 된다.

6. 재귀가 풀리는 4단계 접근법

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

2단계. Base Condition: 답을 바로 알 수 있는 가장 간단한 상황을 생각한다.

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

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

6-1. 재귀를 '굳이' 써야하는 이유

말했다시피 재귀는 효율적이지 않고, 반복문으로 대부분 구현이 가능하다.
아래 경우를 제외하곤, 반복문을 통한 구현이 효율적일 것

꼬리 재귀 최적화: 꼬리 재귀 최적화를 지원하는 컴파일러에 한해 반환값이 재귀 호출 결과값일 때, 재귀 알고리즘을 해석해 반복문으로 바꿔 실행하는 재귀의 성능 문제를 해결한 방식

1. 재귀적 자료구조
자료구조 자체가 재귀적인 경우 재귀 풀이를 적용해야 한다.
ex) 링크드 리스트, 트리, 그리드, 중첩 배열, JSON, HTML 등

2. 재귀적인 풀이 공식
답을 구하는 공식 자체가 재귀적인 경우 사용
ex) 팩토리얼, 피보나치 수열[f(n) = f(n-1) + f(n-2)], 순열/조합

3. 함수형 프로그래밍 : 변수 선언을 금지
불변성(Immutability): 변수 선언을 금지하고, 함수형 프로그래밍에서는 값을 상수로 선언한다.
이 경우 재귀를 사용할 때, 함수를 호출할 때마다 새로운 스코프를 생성하기 때문에, 변수 없이 문제 해결이 가능하다.

6-2. 베이스 조건(Base Condition)

재귀 함수 풀이 시, 재귀함수가 끝나는 종료 조건을 설정해야 함
[주의!]보통 종료 조건을 설정할 때, 재귀의 늪에 빠지게 된다.
"재귀적으로 파고드는게 아니다." -> 재귀의 늪에 빠지게 됨

베이스 조건 설정

"바로 답을 구할 수 있는, 가장 단순한 인풋값을 찾는 것"

-보통 0 or 1
-정수타입 => 인풋이 0 or 1인 상황을 생각
-배열 => 배열의 길이가 0(빈 배열) or 1인 경우를 생각
-트리 => 인풋값이 null or 자식 노드가 null인 경우를 생각
-이차원 배열[=그리드] => 0 0 / 0 1 / 1 0 / 1 1 인 경우 생각

베이스 조건의 return

"문제에서 요구한 답의 데이터 타입을 리턴"

"즉, 문제가 요구하는 데이터 타입 = 베이스 조건 결과 값의 데이터 타입"

-베이스 조건에서 무엇을 리턴하는지 헷갈리면 문제에서 요구한 데이터 타입을 보자
-ex) 트리 / 트리 안 경로의 '노드값 총합(정수)'를 구하는 문제 => 정수타입
-ex) 트리 / 특정 경로의 '트리 노드 자체(노드)'를 구하는 문제 => 트리 노드

6-3. 분해(Decomposition)

"베이스 조건(종료 조건)에 가까워지도록 인풋 값(=인자 값)을 조작

재귀 호출 시, 넣을 인자가 베이스 조건(종료 조건)에 한 단계 더 간단해지도록 조작한다.

재귀적 분해(Recursize Decomposition)
n이라는 정수를 인자로 받았다면, 자기 자신을 호출할 때 n-1을 넣음
어느 순간 인풋값이 베이스 조건에 걸려 재귀 호출이 멈추고, 값을 반환

재귀적 분해의 흔한 패턴
‘분해’도 재귀 문제를 많이 풀다보면 비슷한 패턴이 반복된다.

정수 타입 -> n - 1 or n - 2...
배열 -> 숫자 하나를 떼고 길이를 줄인다. [1,2,3,4] → [2,3,4] → [3,4] 문자열도 마찬가지.
링크드 리스트 -> 포인터가 가리키는 다음 노드, 혹은 다다음 노드를 넣는다.
트리 -> 자식 노드를 넣는다. (이진 트리의 경우 재귀 호출을 2번 하는 경우가 많다.)
‘분해'라고 해서 꼭 값을 줄이는 건 아니다.

"계속 분해하다보면 우리가 원하는 베이스 조건에 도달해야 한다. 그게 중요"

6-4단계. 조합

조합은 재귀 호출이 베이스 조건에 걸려 멈추고 나서, 그 다음에 일어나는 작업

베이스 조건을 기반으로 1단계 위 / 2단계 위 ... 규칙을 찾는다.

재귀적 믿음의 점프(Recursive leap of faith) : 그냥 일단 믿어본다.

7. 예제: 문자열 뒤집기

문자열 s가 주어질 때, s를 뒤집어 반환하는 함수를 만들어라.
ex) reverseString("hello") -> "olleh"

7-1. 재귀를 꼭 써야 하는가?

No -> but 연습을 위해 사용

7-2. 베이스 조건

답을 바로 알 수 있는 가장 간단한 상황은? -> hello 입력을 버리자!
문자열의 길이 = 0 or 1인 경우 "" or "A"

string.length() == 0 -> return ""
string.length() == 1 -> return str;

7-3. 분해

재귀 호출을 거듭해 베이스 조건에 가까워지도록 인풋값을 조작한다.
가장 간단한 것은 앞의 한 글자를 빼고 재귀 호출의 인자로 넣어주는 것

ex) "hello"
"hello" -> "ello" -> "llo" -> "lo" -> "o"

7-4. 조합

부분 답을 가지고 전체 답을 구하는 방법을 생각해본다.

베이스 조건의 바로 윗단계를 생각한다.(string.length == 2)

string.length == 1 -> i -> i = i
string.length == 2 -> hi -> ih = i + h
string.length == 4 -> gray -> yarg = yar + g
length 1로 length 2를 만드는 방법 = 뒤에 h를 붙여준다.

2. 베이스 조건의 세단계 위를 생각한다.(string.length == 4)
>```cpp

length 1로 length 2를 만드는 방법 = 뒤에 h를 붙여준다.

조합의 공통점
일반화할 수 있는 구칙을 찾는다.

"hi" = i + h
"gray" = yar + g

베이스 조건 조절

베이스 조건의 string.length == 1 -> 베이스 조건을 설정하지

func reverseString(s: String) {
    // 베이스 조건	
    if s.count == 0 { return "" }
    // 분해 + 조합
    return reverseString(s.dropfirst()) + s.first!
}

강동현

GAME DESIGN & CLIENT PROGRAMMING

다음 포스트