기초) 재귀 함수와 메모화, 조기 리턴 정리 (중요)

 

 

 

 

 

 

 

세 가지 모두

함수를 활용하는 테크닉의 일종

이라고 한다.

 

 

 

조기 리턴의경우 전반적으로 많이

활용할 수 있는 기초 테크닉이라고

하며

 

 

 

재기 함수와메모화의 경우

일반적인 개발에서는 많이 사용지 않지만

알고리즘을 구현(만들 때) 할 때 매우

유용하므로

 

 

 

대학 과제, 알고리즘 대회,

회사 입사 및 진급 시험 등에 출제되는

알고리즘 문제를 풀기 위해서

반드시 알아야 할 내용이라고한다.

 

 

 

일반적으로 알고리즘에 따라

반복문으로 구현한 코드보다

재귀 호출로 구현한 코드가

좀 더 직관적이고 이해하기

쉬운경우가 많다고 한다.

 

 

 

 

---

 

 

 

 

재귀 함수

 

 

 

 

1. 재귀 호출 사용 개념

 

 

 

함수 내부에서

자기 자신의 함수를 호출하는

함수를 재귀 함수라고하며

 

 

 

이와 같은 호출 방식을

재귀 호출 (recursive call)

이라고 한다.

 

 

 

 

 

 

 

 

 

호출을 하는데

언제 끝낼지 지정을 안 했기 때문에

마지막에 오류가 나는 것을

볼 수 있는데

 

 

 

파이썬은 기본적으로 재귀 깊이가

1000번으로 정해져 있다고 하고

 

 

 

1000번을 초과하면

depth(깊이) 오류가 나게 된다.

 

 

 

그림을 통해 재귀 호출 과정을 알아보자

 

 

 

 

출처 : 파이썬 코딩 도장,  https://dojang.io/mod/page/view.php?id=2352

 

 

 

 

 

 

따라서 반드시

종료 조건을 만들어 줘야 한다.

 

 

 

한번 예제를 보며 코드를 분석해 보자.

 

 

 

 

 

 

 

 

과정을 해석해 보자.

 

 

 

먼저 선언되는 함수의 매개변수(count)에는

호출하는 함수에서 인자 값 5를 전달한다.

 

 

 

첫 count 값은 5!

 

 

 

만약 이 count의 값이 0과 같다면

return(돌아가라 / 멈춰라)라는

조건을 달아주고

 

 

 

count가 0이 아닌 경우

"재귀 몇 번째니?" 와 count의

숫자를 출력해 달라고 요청하는데

 

 

 

이때, count의 수를

별도로 지정해 주지 않는 경우

"재귀 몇 번째니? 5"라는 동일 문구가

1000번 반복된 후 에러가 나 끝나고,

 

 

 

정말 1000 번이 반복되는지

확인하기 위해 count +1을

해주면 5부터 1씩 증가하여

1000까지 반복 호출하다가

에러와 함께 멈춘다.

 

 

 

 

 

 

 

 

 

 

현재 프로그램을 멈추고 되돌아가는

return의 조건은 count 값이

0이 될 때라고 조건을 달았으니

 

 

 

count -=1로 입력하면

종료 조건을 만족하므로

재귀 호출을 끝낼 수 있다.

 

 

 

---

 

 

 

 

2. 재기 함수를 배울 때

가장 기본적으로 배우는 내용은 바로

Factorial (펙토리얼)이라는연산이다.

 

 

 

펙토리얼은 1부터 n까지

양의 정수를 차례대로 곱한 값이며

느낌표(!) 기호로 표기한다.

 

 

 

예 )

5! =5 * 4 * 3 * 2 * 1 = 120

 

 

 

 

 

 

 

---

 

 

 

 

 

펙토리얼의 수학적 정의 1.

 

 

n! = 1*2*3...*(n-2)*(n-1)*(n)

 

 

 

 

 

펙토리얼의 수학적 정의 2.

 

 

*아래 두 방법을 사용하여 정의하는 것을

수학적 귀납법이라고부른다.

 

n! = n * (n-1)!

0! = n

 

 

 

 

프로그래밍에서의 펙토리얼은

위 두 가지 정의 방법을 모두

많이 사용한다.

 

 

 

 

 

위 식을 코드로 작성해 보면

 

 

 

 

1. n! = 1 * 2 * 3 *...(n-2) * (n-1) * n

 

 

 

def factorial_1(n):

변수 = 1

for i in range(1, n + 1):

변수 *= i

return 변수

 

 

 

 

 

2. 0! = 1

n! = n * (n-1)!

 

 

 

def factorial_2(n):

if n == 0:

return 1

else:

return n * factorial_2(n - 1)

 

 

 

 

 

 

 

 

 

와 같으며

 

 

 

두 번째 정의의 경우, 마찬가지로

함수 내부에서 (factorial_2(n))

자신의 함수를 호출하고 있는 (factorial_2(n-1))

재귀 호출의 형태를 볼 수 있다.

 

 

 

한번 인자 값을 넣어 함수를 출력해 보자.

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

재귀 함수의 문제점

 

 

 

 

 

자주 언급되는 예제로

피보나치수열 (fibonacci)이

등장하는데

 

 

 

토끼가 어떤 속도로 번식하는가라는

연구에서 나온 수열이라 하며

 

 

 

 

 

 

 

 

앞쪽에 있는 것을 더하며

나아가는 특이한 함수이다.

 

 

 

먼저

이 피보나치의 수열을 계산하는

식을 코드로 작성해 보자.

 

 

 

 

 

 

 

 

 

 

 

적은 수를 더하는 것은

별 문제가 없는 듯 보이지만

 

 

 

가령,

 

 

 

 

 

 

 

 

 

높은 숫자의 피보나치 수를 구하게 되면

결과가 더디게 나오기 시작한다.

 

 

 

현재 화면상의 출력값을 보면

92247465는 피보나치 값,

 

 

 

그 아래에 18454929는

바로 35라는 피보나치 수를

구할 때 실행한 덧셈 반복 횟수이다.

 

 

 

덧셈 횟수가 기아 급수적으로 늘어나는 이유는

트리 형식이라 부르는 피보나치의 계산 방법

때문인데

 

 

 

*트리 형식 :

전에 구했던 값을 다시 여러 번 반복하여

구하는 구조 : '노드' 값을 구하기 위해

'리프' 값 들을 더한다는..

 

 

 

이로 인해 어쩔 수

없이 일어나는 현상이다.

 

 

 

이처럼 많은 연산이 반복적으로

이루어지는 것은 효율성 면에서

결코 좋지 않은 것으로

 

 

 

바로 이러한 문제를 해결하기 위해

사용되는 방법이 바로 memorization,

즉 메모화라는 기능이다.

 

 

 

 

 

* 번외 팁

 

 

 

위 피보나치 예제를 보면

덧셈 횟수를 확인하기 위해

counter라는변수를 사용했음을

볼 수 있는데

 

 

파이썬에서 함수 외부에 있는

변수를 함수 내부로 가지고 와

사용할 때는 반드시 global

이라는 키워드를 사용해야 한다.

 

 

 

global 키워드를 사용하지 않은 채

변수를 사용하면.

 

 

 

 

 

 

 

이와 같은 Error를 만날 수 있다.

 

 

 

하지만 예외가 있다!

 

 

 

아래 살펴볼 메모화 예제에

동일하게 외부 변수를 함수 내에

가지고 와 사용해야 하는데

 

 

 

이때는

global 키워드를 사용하지

않아도 적용이 가능하다.

 

 

 

바로 reference를 나타내는 자료형의

경우 global을 입력하지 않아도

된다는 것!

 

 

 

초반에는 구분이 어렵기 때문에

간단히 오류가 발생하면 global을

넣어주고 오류 없이 돌아가면

그대로 잘 사용하자.

 

 

 

 

 

---

 

 

 

 

Memorization (메모화)

 

 

 

 

먼저 외부에 '메모'로 사용할

딕셔너리를 만들어 준다.

 

 

 

딕셔너리의 키와 값으로는

f1 일 때 1, f2였을 때 1

의 값을 미리 넣어준다.

 

 

 

이어서 f라는 함수를 정의해 주고

만약 n이 메모에 있는 경우

 

 

 

return을 사용해서

메모에 n을 리턴해 주고

아닐 경우 계산을 직접 해준다.

 

 

 

f(n-1) + f(n-2) 계산식을

output이라는 변수에 넣어주고

이를 리턴한다. return ouput

 

 

 

이렇게 한번 계산한 값 output은

메모[n]에 넣어준다.

 

 

 

 

 

 

 

 

 

 

쾌적하게 돌아간다!

 

 

 

이미 한번 계산했던 것은

더 계산하지 않고 메모에

있던 것을 확인하기 때문.

 

 

 

 

이처럼

재귀 함수를 사용을 할 때

계산 시간이 오래 걸린다면

반드시 메모화를 함께 사용해야 한다.

 

 

 

---

 

 

 

 

 

조기 리턴

 

 

 

 

return의 특성을 생각하면

조건이 부합한 경우 return 후의

코드는 실행이 안된 채

프로그램이 종료된다.

 

 

 

이 점을 활용하면

불 필요하게 나누어진 코드 블럭을

하나로 합쳐 작성할 수 있으며

 

 

 

그 결과

들여쓰기 단계를 한 단계 줄여

코드 작성이 가능해지는데

 

 

 

이와 같은 방식으로 작성되는 코드가

더 좋은 코드로 여겨진다고 한다.

 

 

 

아래 동일한 결과를 내는 두 코드를

비교해보자.

 

 

 

 

 

 

 

 

 

 

 

if 와 else

두 개의 코드 블럭으로 나누어진 것을

return의 특성을 고려해 else를 없애주고

하나의 블록으로 합쳐주었다.

 

 

 

이처럼

블럭 내부의 코드 실행 흐름 중에

return 키워드를 앞부분에 넣어

이후에 실행될 함수를 조기에

차단하는 것을 조기 return

이라고 부른다.

 

 

 

파이썬은 기본적으로 들여 쓰기가

적용되어 코드가 작성되곤 하는데

조기 리턴을 활용해 들여 쓰기의

단계를 줄여줄 수 있는 코드가

훨씬 더 좋은 코드라고 하니

참조하자!

 

 

 

 

 

---

 

 

 

 

 

 

도움 : 유튜브 혼자 공부하는 파이썬 윤인성님

https://www.youtube.com/watch?v=rJALa9MW7M4&list=PLBXuLgInP-5kr0PclHz1ubNZgESmliuB7&index=37