10. Algorithms - Recursive Function

재귀함수(Recursive Function)란

자기 자신을 부르는 함수이다. 

 

재귀함수의 의미는 무엇인가

재귀함수는 귀납적 계산 방법(귀납적 문제해결 방법)이라고 할 수 있다. 

계산 방법에는 순차적 계산 방법과 귀납적 계산 방법 이라는 두 가지 방식이 있다. 

먼저 순차적 계산 방법은 

1. A를 계산한다. 

2. A를 이용해서 B를 계산한다. 

3. B를 이용해서 C를 계산한다 

4. C를 이용해서 D를 계산함으로써 원하는 결과를 얻는다. 와 같이 순차적으로 진행하는 계산 방식이다. 

예를 들어 n! = n x (n-1) x(n-2) ... x 2x1 과 같이 Factorial을 계산 하는 방법을 일컫는다. 

 

두번째는 귀납적 계산 방식이다. 이는

1. 구하려고 하는 값을 f(x)라고 한다. 

2. 그러면 f(x)를 구하기 위해 또 다시 f(x)를 활용하는 것이다. 

예를 들어 n! = n x (n-1)! 즉, f(x)를 x의 Factorial 값을 구하는 함수라고 하면, 앞의 식은 f(n) = n x f(n-1) 로 계산할 수 있고, 이러한 방식을 말한다. 

귀납적 계산 방식을 예를 들어 더 알아보자

ex. n^m을 귀납적으로 계산하여라 라는 문제가 있을 때, 

귀납적 계산 방식을 사용하면 위의 방식을 적용했을 때 => n^m = n x n^(m-1)이 된다. 

다시 말해, n^m이 n을 m 번 곱하는 거라는게 성립하려면, n^(m-1)이 n을 m-1번 곱하는 것이라는 가정이 먼저 성립해야 한다. 

이 가정이 성립함을 알려면 '왜 귀납적 계산법이 제대로 된 값을 반환하는가?' 를 보이면 될 것이다. 

왜 귀납적 계산법이 제대로 된 값을 반환하는가?'=> 왜냐하면 수많은 가정을 하다가 맨 끝에는 정확한 값이 있기 때문이다. 

예시로 보면, n! = n x (n-1)! 이라는 수많은 가정을 하면서 계속 재귀 속으로 들어가다가 

맨 끝에는 0! == 1이라는 정확한 값이 있으니까 지금까지 해 왔던 수많은 'n^m이 n을 m 번 곱하는 거라는게 성립하려면, n^(m-1)이 n을 m-1번 곱하는 것이라는 가정' 이 성립됨이 쫙 보여지면서 결국엔 제대로 된 값을 반환하게 되는 것이다.

 

 

재귀함수의 디자인 절차

1. 함수의 역할을 말로 정확하게 정의한다. 

2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다. (이때 기저조건은 보통 '해보나마나한 뻔하고 가장 기본이 되는 것'이 된다. )

3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. 

 

아래에서 예시를 통해 위의 디자인 절차대로 재귀 문제를 풀어보자. 

예1) n^m으르 재귀함수를 이용하여 계산하라. 

1. 함수의 역할을 말로 정확하게 정의한다. => getPower(n, m) : n^m의 값을 반환하는 함수
2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다.  => getPower(n, 0) = n^0 = 1 이므로 위의 정의대로 했을 때 잘 작동한다. 
3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. => getPower(n, m) = n x getPower(n, m-1)

function getPower(n, m){
     if(m===0){
    	return 1;
     }
     else{
     	return getPower(n, m-1) * n;
     } 
}

예2) N to M: N~M 까지의 합을 구하라.

1. 함수의 역할을 말로 정확하게 정의한다. => getSum(n, m): n 부터 m 까지의 합을 구하는 함수
2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다.  => getSum(n, n): n 
3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. => getSum(n, m) = getSum(n, m-1) + m

function getSum(n,m){
   if(n===m){
    	return n;
    }
    else{
    	return getSum(n, m-1)+m;
    }
}

 

예3) 각 자릿수의 합: 십진수 N을 입력받아 각 자릿수의 합을 구하라.

1. 함수의 역할을 말로 정확하게 정의한다. => getDigitSum(x): x의 각 자리수의 합을 반환하는 함수
2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다.  => getDigitSum(x) = x
3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. => getDigitSum(x) = getDigitSum(x/10) + (x%10)

function getDigitSum(x){
   if(0<=x && x<=9){
    	return x;
    }
    else{
    	return getDigitSumm(x/10)+(x%10);
    }
}

예4) 이진수 출력하기: 십진수 N을 입력받아 이진수로 출력하시오

1. 함수의 역할을 말로 정확하게 정의한다. => PrintBinary(x): x을 이진수로 출력하는 함수
2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다.  => PrintBinary(1) = 1, PrintBinary(0) = 0
3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. => PrintBinary(x) = PrintBinary(x/2)console.log(x%2)

function PrintBinary(x){
    if(x===0){
    	console.log(0)
    }
    else if(x===1){
    	console.log(1)
    }
    else{
    	PrintBinary(x/2);console.log(x%2);
    }
 }
     

예5) 팰린드롬인지 판별하기

1. 함수의 역할을 말로 정확하게 정의한다. => isPalindrome(myString, start, end): myString의 start부터 end까지가 팰린드롬이면 true, 아니면 false을 반환한는 함수
2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다.  => isPalindrome(myString, index, index) = true
3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. => isPalindrome(myString, start end){
if (myString[start] === myString[end]) return isPalindrome(myString, start+1, end-1)
else return false
}

function isPalindrome(myString, start, end){
     if(start === end){
    	return true;
     }
     else{
     	if(myString[start] === myString[end]) {
        	return isPalindrome(myString, start+1, end-1);
         }
         else{
         	return false;
         }
     }
 }