[자료구조와 알고리즘] 재귀 알고리즘 깊이 있게 다뤄보기(1)

Source: https://velog.io/@yonghyeun/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%9D%98-%EC%9E%A5%EC%A0%90%EA%B3%BC-%EB%8B%A8%EC%A0%90-%ED%95%B4%EA%B2%B0%EC%B1%85

 

재귀 문제에는 두가지 카테고리를 소개한다.

바로 반복 실행과 계산이다.

 

 

재귀 카테고리 1. 반복 실행

 

제자리(in-place) 수정

 

배열 내 값을 두배로 만드는 과정을 예시로 들어보자.

배열 [ 1,2,3,4,5 ]를 두 배로 만들어 [2,4,6,8,10]이라는 배열이 나오도록 구현해보자.

 

1. 첫번째 방법은 원래 배열은 그대로 두고 두배로 만든 데이터를 포함하는 새 배열을 생성하는 것이다.

 

a = [1,2,3,4,5]

b = double_array(a)  -> [2,4,6,8,10]

 

2. 두번째 방법으로는 제자리 수정이다. 실제 함수에 전달된 원본 배열을 바꾸는 개념이다.

 

a # [2,4,6,8,10]

b # [2,4,6,8,10]

 

제자리 함수는 실제로 a를 수정했고, b는 a와 같은 배열을 가리킨다.

 

 

재귀 함수에 인자를 추가하기

재귀 함수에서 인수는 배열이 주어진다.

여기서 인자를 하나 더 전달하면 인덱스를 기록하고 증가시킬 수 있다.

 

def double_array(array, index=0):
	if index >= len(array):
    	return
    
    array[index] *= 2
    double_array(array,index + 1)

 

재귀 카테고리 2. 계산

 

 

계산 방식에는 두 가지 계산 방식이 존재한다. (상향식과 하향식 계산 방법)

먼저 하위 문제에 기반해 계승을 계산하는 접근법을 알아보자.

 

하위 문제란? :

하위 문제란 입력을 더 작게 한 똑같은 문제다.

재귀가 유용하게 쓰이는 또 하나의 영역은 하위 문제의 계산 결과에 기반해 계산할 수 있을 때이다.

 

 

예를 들어)

 

factorial(6)은 6*5*4*3*2*1 이고

factorial(5)는 5*4*3*2*1 이다.

factorial(6)은 6* factorial(5) 와 같다고 할 수 있다.

factorial(5)는 더 큰 문제의 결과를 계산하는데 쓰이는 더 작은 문제이므로, factorial(6)의 하위 문제이다.

 

 

상향식과 하향식 계산 방법

상향식과 하향식 모두 재귀로 작성이 가능하다.

상향식에서는 루프를 쓰든 재귀를 쓰든 같은 전락으로 계산하지만,

하향식 계산 전략을 구현할 방법은 재귀 뿐이다.

 

여기서 하향식 방식은 문제를 해결하는데 있어 새로운 사고 전략을 제공한다.

하향식 사고 방법에 대해 구체적으로 알아보자.

 

 

하향식 재귀

하향식 사고 방식이 어떻게 새로운 사고 방식을 제공할까?

 

핵심을 먼저 말하자면,

다른 함수를 호출하는 코드를 작성할 때는 내부적으로 어떻게 동작하는지 모르더라도

그 함수가 올바른 값을 반환하리라고 가정한다.

즉, 실제 내부 함수가 이미 작성되어 있다고 가정하고 코드를 작성해 나가는 것이다!

 

하향식 사고 절차

 

1) 배열의 합

 

배열 내 모든 수를 합하는 sum이라는 함수를 작성한다고 가정해보자.

array = [1,2,3,4,5]

해당 배열을 함수에 전달하면 모든 수의 합인 15를 반환한다.

 

1. 작성 중인 핵심 함수 sum()을 이미 누군가 구현해 놓았다고 가정.

2. 문제의 하위 문제 찾기 -> [2,3,4,5]

3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하기.

sum 함수는 잘 동작하고 있으며 하위 문제가 [2,3,4,5] 이면 2+3+4+5의 값이 나올 것이다.

 

def sum(array)
	# 기저조건 추가: 원소가 하나 남았을 때
	return array[0] if array.length == 1
    
	return array[0] + sum(array[1, array.length -1])
end

 

값	하위 문제	array[0]	결과 값
12345	2345	1	1+2345 =1+14=15
2345	345	2	345+2 =12+2 =14
345	45	3	45+3 =9+3 =12
45	5	4	5+4 =9
5	기저조건	5	5

 

5 = 5

45 = 5+4 = 9

345 = 45+3 -> 9+3 =12

2345 = 345+2 -> 12+2 =14    

12345 = 2345+1 -> 14+1 =15

 

맨 마지막 결과 값인 5 부터 값이 치환된다고 생각하면 쉽게 접근 할 수 있다.

맨 마지막 결과 값에서 위로 갈 수록 값이 치환되어 최종 결과 값을 도출해낼 수 있다.

최종 연산으로 15가 도출된다.

 

 

 

2) 문자열 뒤집기

"abced" 라는 인수를 받으면 "decba"를 반환한다.

 

1. 작성 중인 핵심 함수 reverse()를 이미 누군가 구현해 놓았다고 가정.

2. 문제의 하위 문제 찾기 -> "bcde"

3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하기.

 

def reverse(string)
	return string[0] if string.length == 1 # 기저조건
	return reverse(string[1:] + string[0])
end

 

 

입력 값	하위문제	string[0]	결과
abcde	bcde	a	bcdea
bcde	cde	b	cdeb
cde	de	c	dec
de	e	d	ed
e	기저조건	e	e

 

연산을 진행하면서 하위 값들이 입력 값에 새로운 값을 집어 넣는다고 생각하면 된다.

 

e = e

de = e+d = ed

cde = de+c = e d+c = edc

bcde = cde+b = edc+b = edcb

abcde = bcde+a =  edcba 

 

bcde(cde((de=e+d)+c)+b) + a

그래서 최종 연산으로 edcba 가 도출된다.

 

 

 

 

 

참고 자료

https://product.kyobobook.co.kr/detail/S000001834743

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

 

https://adjh54.tistory.com/194

[Java/알고리즘] 재귀 함수(Recursion Function) 이해하기