https://www.youtube.com/watch?v=gFpKGWdEE5g&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=17

17강 재귀 함수-0
17강 재귀 함수-1

재귀 함수의 대해서

재귀 함수란

17강 재귀 함수-4

이에 대해 꼭 이해하고

17강 재귀 함수-6

recursive라는 단어는 재귀적이라는 의미를 가지고 있는데요 실제로 우리가 프로그램을 작성할때 재귀적으로 작성한다 혹은 recursive 하게 동작하도록 한다 이런 의미가 들어가 있으면 재귀 함수를 이용하는 거라고 볼수 있습니다

17강 재귀 함수-8

재귀 함수 예제

17강 재귀 함수-10

이 함수에서는 어떤 문장을

17강 재귀 함수-12

메인 함수 안에서 호출하게 되면

17강 재귀 함수-14

무한이 출력하게 되는거죠

17강 재귀 함수-16

프로그램이 종료될 수 있습니다

17강 재귀 함수-18

오류메세지와 함께 종료되는 것을 확인 할 수 있습니다

17강 재귀 함수-20

maximum recursion depth exceeded 라고 나오는걸 확인할 수 있습니다.

즉 최대 재귀 깊이가 초과 되었다는 메세지가 출력이 되고 있는건데요

17강 재귀 함수-23

함수를 재귀적으로 호출하게 되면 오류메세지가 나올수 있습니다

17강 재귀 함수-25

스텍 프레임에

17강 재귀 함수-27

함수까지 처리가 되는 방식 실제로는 스텍과 같은형태로 동작한다고 이해할수 있습니다.

즉 일종의 스텍 자료구조안에 함수에

17강 재귀 함수-30
17강 재귀 함수-31
17강 재귀 함수-32

같은 재귀 깊이 제한을 걸어 둘수가 있는 겁니다

그래서 만약 우리가 제한 없이 재귀 함수를 호출 하고자 한다면 이러한 재귀 재한을

느슨하게 만드는 방법을 이용하거나 별도로

17강 재귀 함수-36

코딩테스트 수준에서는 이와같이 일번적인 재귀 함수를 사용해도 통과할수 있도록 출제 되는 경우가 많습니다

17강 재귀 함수-38

내용을 반복하도록

17강 재귀 함수-40

와일이나 포문을 이용

17강 재귀 함수-42

17강 재귀 함수-44
17강 재귀 함수-46

사용할때는 재귀 함수의 종료조건을 반드시 명시할 필요가 있습니다.

17강 재귀 함수-48

값을 반환할수 있도록 만들어야 됩니다

그래서 이러한

17강 재귀 함수-51

함수가 무한 호출 될수

발생할수 있습니다

17강 재귀 함수-54

종료조건을 명시해서 특정한 조건을 만족한다면 함수가 종료될수 있도록 만들수 있습니다

17강 재귀 함수-56

이렇게 전달 받은 i라는 매개변수의

17강 재귀 함수-58

현재 예시에서는 i번째 재귀함수에서

재귀함수를 호출하도록 만드는걸

17강 재귀 함수-61

i가 들어왔을때

다음 재기함수를 호출 하도록 만들면 이렇게재귀함수가

17강 재귀 함수-64

i값이 차례대로 증가하기 때문에

재귀 함수가 호출된 뒤에 이 100번째 재귀 함수는 바로 종료될 수 있도록 만들수 있습니다

17강 재귀 함수-67

만족되었는지 확인하는 방식으로

작성할수 있습니다

17강 재귀 함수-71
17강 재귀 함수-72
17강 재귀 함수-73

실행을 해보시면

재귀함수에서 두번째를 호출하고 또 이어서

두번째는 또 3번째를 호출 하는 방식을 반복해서 결과적으로

100번째 재귀 함수가 호출 되었을때 이 100번째 재귀함수는 바로 종료조건의

17강 재귀 함수-78
17강 재귀 함수-79
17강 재귀 함수-80

재귀 함수를

17강 재귀 함수-82

이렇게 차례대로 호출이 되었다가

17강 재귀 함수-84

그시점에 함수까지

17강 재귀 함수-86
17강 재귀 함수-88

재귀 함수를 이용하는

팩토리얼 구현 예제

17강 재귀 함수-91

기호를 이용해서

차례대로 곱한결과 라고 볼 수 있습니다.

17강 재귀 함수-94

0 팩토리얼과 1팩토리얼 값은 1임

17강 재귀 함수-96

단순히 반복문을 이용해서 즉 iterative

17강 재귀 함수-98

값이 이 result에 값으로 1을 넣어준뒤에

전부다 이 result에

17강 재귀 함수-101

모두 곱해진 결과가 반환 되겠죠

반면에 재귀적으로 구현하고자 할때는

이용해서 구현할 수 있습니다.

17강 재귀 함수-105

자기자신 n에다가

팩토리얼을 호출한 값을 곱한 결과를 확인할 수 있습니다

17강 재귀 함수-108

이 4 팩토리얼은 또 재귀적으로함수가 실행되어 4곱하기 3팩토리얼의 값이 반환됩니다

그래서 결과적으로 이렇게 1팩토리얼이 호출된 시점에서 기본적으로 1팩도리얼의 값은 1이기 때문에 이와 같이 1을 반환하는 것을 확인 할 수 있습니다

17강 재귀 함수-111
17강 재귀 함수-112

재귀 함수를 이용해서 마찬가지로 팩토리얼을 구현할수 있다는것까지 확인해보았습니다

다만 이렇게 수학적으로 정의된 식을 그대로 이용한다는 점에서 실제로 반복문을 이용해서 작성할때보다 코드가 더 간결하고 직관적일 수 있다는 점을 확인 할 수 있습니다

17강 재귀 함수-115
17강 재귀 함수-116

5팩토리얼의 값으로 확인할 수 있습니다

17강 재귀 함수-118

https://www.youtube.com/watch?v=R1gxRwXRpMQ

유클리드 호제법 설명

17강 재귀 함수-121

재귀 함수를 유클리드 호제법에 대해서

17강 재귀 함수-123
17강 재귀 함수-124

약수 중에서 가장 큰값을 의미

17강 재귀 함수-126

이때 여기에서 크다고 할게요

이때 a를 b로 나눈 나머지를 R이라고 합시다

17강 재귀 함수-129

a와 b에 최대공약수는 b와 r에 최대공약수와 같다는 점입니다

17강 재귀 함수-131

수학적으로 증명할 수 있는내용이지만

재귀함수로 구현을 해서

17강 재귀 함수-134
17강 재귀 함수-135

Gcd라는 것은 그레이스트 커먼 디바이저

실제로 단순히 gcd라고 하면 최대공약수를 의미하는 경우가 많습니다

자그래서 한번 192와 162의 최대공약수를 구해보도록 할게요 자 이때 우리가 알수 있는점은 192와 162의 최대 공약수는 192를 162로 나눈 나머지 30을 구한뒤에

17강 재귀 함수-140

같은 값을 가진다는 것을 알수 있습니다

17강 재귀 함수-142

그다음 또 마찬가지로 162와 30의 최대공약수는 30과 12에 최대공약수 와 같습니다

또 마찬가지로 이것은 12와 6의 최대공약수와 같이때문에

결과적으로우리는 192와 162의 최대공약수가 12와 6의 최대공약수와

같다는걸 알아낼수 있습니다

17강 재귀 함수-147

재귀함수를 이용해서 이러한 과정을 직관적으로 코드로 옮길수 있습니다

자 그래서 결과적으로 12는 6의 배수이기 때문에 이때 이 6을 최대 공약수라고 말할수 있습니다.

17강 재귀 함수-150
17강 재귀 함수-151
17강 재귀 함수-152
17강 재귀 함수-153

비를 반환 할수 있도록 하고요

나눈 나머지에 를 반환할 수 있도록하면 이러한 수학적 로직을 그대로 이용 할 수 있는겁니다.

17강 재귀 함수-156

출력된걸

17강 재귀 함수-158

이함수의 동작과정상

17강 재귀 함수-160

그냥 a와b를 이렇게 인자값으로

17강 재귀 함수-162

자 이러한 재귀함수는 수학적으로 정의된 어떠한 점화식 과 같은 형태를 간단히 코드로 옮길수 있도록 해준다는 점에서

17강 재귀 함수-165

다시말해 재귀함수를 잘 활용하게 되면 복잡한 알고리즘도 간결하게 작성할 수 있음

17강 재귀 함수-167

코드가

17강 재귀 함수-169

이론적으로 모든 재귀함수는

반대로 반복문을 이용해 구현된 코드도 재귀함수를 이용해 구현 할수 있습니다

17강 재귀 함수-173

재귀함수가 반복문 보다 유리한경우도

문제를 풀기위해 더좋은

17강 재귀 함수-176

문제를 푸시는걸 추천 드립니다

17강 재귀 함수-178

구현상 스택자료구조를 사용하지 않고

17강 재귀 함수-180

대표적으로 DFS를

단순히 재귀함수를 이용해서 DFS를 구현하곤 합니다

17강 재귀 함수-184

재귀 함수를

바르게 이해하고 넘어가는걸 추천함

Last Updated:

Summarize & share videos seamlessly

Loading...