(1주차 2차) 재귀호출

순환(Recursion)

알고리즘이나함수가수행중에자기자신을다시호출하여 문제를해결하는프로그래밍기법

>재귀호출이라고도함

>정의자체가순환적으로되어있는경우 적합함

 

순환의 예

팩토리얼 값구하기

피보나치수열

이항계수

하노이의 탑

이진탐색

영역채색(Blob Coloring)

 

팩토리얼의 정의

n! = 1 𝒏 = 0

       𝒏* (𝒏– 1)! 𝒏 ≥ 1

 

(n-1)! 을구하는서브함수factorial_n_1를따로제작

 

 

순환 호출의 내부적인 구현

>순환호출시복귀주소가시스템스택에저장되고호출되는 함수를위한매개변수와지역변수를스택으로부터할당받음

 - 함수를위한시스템스택에서의공간을활성레코드 (Activation Record)라함

>호출된함수가끝나게되면시스템스택에서복귀주소를추출하여 호출한함수로되돌아가게됨

>순환호출이계속중첩될수록시스템스택에서는활성레코드들이 쌓이게됨

 

순환 알고리즘의 구조

 

순환알고리즘의구조이해

int factorial(int n)
{
if( n <= 1 )
return 1; ← 순환을멈추는 부분
else
return n * factorial(n-1); ← 순환호출을 하는 부분
}

>>>만약순환호출을멈추는부분이없다면? 시스템오류발생시까지 무한정호출하게됨

 

순환과 반복

컴퓨터에서의되풀이: 순환과반복

 

순환(Recursion)

순환호출이용

  - 순환적인문제에서는 자연스러운방법

  - 함수호출의오버헤드

 

반복(Iteration)

for나while을이용한반복

  - 수행속도가빠름

  - 순환적인문제에서는 프로그램작성이 아주어려울수도있음

 

>대부분의순환은반복으로바꾸어작성할수있음

>순환호출이끝에서이루어지는순환을꼬리순환(Tail Recursion)이라함

 

 

팩토리얼의 반복적 구현

 

n! = 1                                   𝒏 = 1

       𝒏* (𝒏– 1) * (𝒏–2)… * 1  𝒏 ≥ 2

int factorial_iter(int n)
{
int k, v=1;
for(k=n; k>0; k--)
v = v*k;
return(v);
}

 

피보나치수열

 

>피보나치 수열의 계산

 

순환호출 사용시 비효율적인예

 

fib(n)            0             𝒏 = 0

                    1             𝒏 = 1

         fib(𝒏–2) + fib(𝒏– 1) otherwise

 

intfib(intn)
{
if( n==0 ) return 0;
if( n==1 ) return 1;
return (fib(n-1) + fib(n-2)); 
}

같은항이중복해서계산됨

예) fib(6)을호출하게되면fib(3)이3번중복계산됨

같은항이중복해서계산되는현상은n이커지면더욱심해짐

 

>피보나치수열의 반복구현

 

하노이탑

하노이탑 문제

>문제는막대A에쌓여있는원판n개를막대C로옮기는것

 한번에하나의원판만이동가능

 맨위에있는원판만이동가능

 크기가작은원판위에큰원판이쌓일수없음

 중간막대를임시적으로이용할수있으나앞조건들을지켜야함