재귀함수 잘 만들기

재귀함수가 필요한 경우

 

1. 반복적인 작업이필요한 경우

ex) 팩토리얼

 

2. 하위문제의 계산결과를 통해 계산할 수 있는 경우

ex) 숫자의 합 구하기, 숫자 배열에서 최대값 구하기

 

재귀가 필요한 조건을 구분하는 것이 가장 어려운 부분인 듯 합니다.

특히 DP와 관련된 여러 문제를 다루어보면서 어떤 경우에 재귀를 사용해야할지 판단하는 것을 연습하는 것이 필요할 듯 하네요

 

---

재귀함수에 대한 오해

- 루프를 사용한 코드보다 무조건 빠르다? 

경우에 따라 다르다.

 

- 재귀함수 안에서는 루프를 쓰면 안된다?

아니다.

 

---

재귀함수 만드는 방법

상향식(Bottom-up), 하향식(Top-down) 두 가지 방식이 있습니다.

일반적으로 바텀-업 방식은 루프에 비해 딱히 장점이 없고, 코드가 간결하지 못하기 때문에

탑-다운 방식을 많이 사용합니다.

 

탑다운 방식으로 재귀함수를 쉽게 만드는 방법은 아래와 같습니다.

 

1. 만들고자 하는 함수가 이미 구현되어 있다고 가정

2. 문제의 하위문제를 찾을 것

3. 하위문제에 함수를 호출하는 것부터 시작

4. Base case 찾기 : 재귀를 더이상 사용하지 않고 탈출하고자 하는 조건 부여하기

**

컴퓨터는 스택을 이용하여 호출중인 함수에 대해 call stack에 기록합니다.

재귀함수에서 탈출하지 않는다면 무한대로 메모리에 call stack이 늘어나게 되고, 결국 stack overflow 오류가 발생하게 됨!

**

 

 

위의 내용을 바탕으로 숫자의 배열을 전달받아서, 합계를 리턴하는 sum 함수를 구현하려고 합니다.

주어진 배열이 [1,2,3,4,5]라고 했을 때

 

1. sum 함수가 이미 있다고 가정

2. [2,3,4,5]가 하위문제이고, 이 문제의 계산결과에 1을 더하면 내가 원하는 문제 [1,2,3,4,5]의 합을 계산한 값을 구할 수 있을 것임

// Pseudocode

return array[0] + sum(array의 인덱스0을 제외한 나머지)

3. 함수를 만들고, 하위문제를 호출해보기 (swift로 작성)

func sum(_ array:[Int]) -> Int {
	var resultArr = array
	let indexZero = resultArr[0]
	resultArr.removeFirst()
	return indexZero + sum(resultArr)
}

4. BaseCase 찾기

이 문제의 경우, 전달받은 배열의 원소가 1개일 때 원소의 값을 리턴하고 재귀 종료하면 될 것이다!

func sum(_ array:[Int]) -> Int {
	if array.count == 1 { //BaseCase
		return array[0]
	}
	var resultArr = array
	let indexZero = resultArr[0]
	resultArr.removeFirst()
	return indexZero + sum(resultArr)
}

 

 

 

간단한 예시로 살펴봤지만 복잡한 문제라고 해도 위의 방법으로 해결이 가능합니다.

중요한 것은 재귀가 필요한 경우인지를 파악하는 것,

basecase를 찾는 것

두 가지가 될 것이고 

상황에 따라 다르게 생각해야 되는 부분이기 때문에 어떤 해답이 있지는 않겠네요