Recursive(재귀 함수)

Recursion : 자기 자신을 호출하는 함수를 지칭함

ex)

func() 

{

print("hello world!");

func();

}

무한루프를 방지하기 위한 조건

• base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함
• Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 함

순환 함수와 수학적 귀납법

- ex) 

• 정리: func(int n)은 음이 아닌 정수 n에 대해 0~n 까지의 합을 계산한다

• 증명:
1. n=0인 경우 0을 반환
2. 임의의 양의 정수 k에 대해 n<k인 경우 n 까지의 합을 올바르게 계산한다고 가정한다
3. n=k인 경우 func는 먼저 func(k-1)을 호출한다. 이는 2번 가정에 의해 0부터 k-1 까지의 합이 올바르게 계산된다. 메서드 func는 그 값에 n을 더해 반환하므로 func는 0부터 k 까지의 합을 올바르게 계산한다.
   

재귀 함수의 장단점

• pros: 단순하고 알기 쉽게 표현이 가능하다
• cons: 오버헤드가 발생하여 성능에 영향을 미친다(parmeter 전달, function call로 인한 stack 참조 및 리턴)

재귀 함수의 예

Factorial : n!

0! :1

n! = n*(n-1)!

x^n

x^0=1

x^n= x*(x*(n-1))

Fibonacci number

f0=0

f1=1

fn=f(n-1)+f(n-2)

최대공약수(Euclid method)

func gcd(int m, int n) {  

// m>=n인 양의 정수 m, n에 대해 m이 n의 배수라면

// gcd(m,n)=n이고, 그렇지 않으면 gcd(n,m%n)이다

if(n>m)

swap(m,n);

if(m%n==0)

return n;

else 

return gcd(n,m%n);

}

gcd: 단순한 버전

func gcd(int p, int q){

if(q==0)

return p;

else

return gcd(p, p%q)l

}

이진법 변환 출력

func toBinary(int n){

// 13을 예로 들자면,  13 -> 6 -> 3 -> 1로 toBinary() 함수가 호출되며

// n==1인 상태에서 print(1)이 출력됨. 이는 13을 2로 3번 나눈 후의 나머지와 동일하다.

// 즉 , 13의 이진법인 1101을 1*2^3 + 1*2^2+0*2^1+ 1*2^0을 뒤집은 형태로 이해하면 된다

if (n<2)

print(n);

else{

toBinary(n/2);

print(n%2);

}

}

재귀 함수 설계 tip

• base case와 recursive case를 정확히 명시

• 암시적(implict) 매개변수를 명시적(explict) 매개변수로 바꾸어라
  

암시적 매개변수를 명시적 매개변수로 바꾼다?

ex)

int search(int [] data, int n, int target) {

for( int i=0; i<n; i++) { 

if(data[i] == target) {

return i;

}

return -1;

}

위와 같은 순차탐색에서 배열의 시작점인 0은  보통 생략하는데 이를 암시적 매개변수라 한다.

int search(int [] data. int begin, int end, int target) {

if(begin > end) {

return -1;

}

else if(target == data[begin]) {

return begin;

}

else

return search(data, begin+1, end, target);

}

이런식으로 시작과 끝 인덱스를 명시적으로 표현할 수 있다. 이는 이전의 반복문을 통한 순차탐색과 동일한 일을 수행한다. 명시적으로 시작과 끝을 지정하면 재귀적으로 base case를 정확하게 지정할 수 있다. 물론 꼭 시작점을 명시하지 않아도 코드를 작성할 수는 있지만 명시적으로 지정하면 더 이해하기도 쉽고 코드도 간결해진다.

int search( int [] data, int begin, int end, int target) {

if(begin>end) {

return -1;

}

else if(target == data[end]) {

return end;

}

else 

return search(data, begin, end-1, target);

}

이런식으로 재귀 함수의 형태를 다르게 정의하기도 하고

int search( int [] data, int begin, int end, int target) {

if(begin>end) {

return -1;

}

else {

int middle= begin+end/2;

if(middle == target)

return middle;

int inex= search(data, begin, middle-1,target);

if(index!=-1)

return index;

else

return search(data, middle+1, end, target);

}

}

이런식으로 이진탐색? 비슷하게 명시적으로 재귀의 범위를 지정할 수 있다.