Recursion

1. 기본 개념

• 간단하게 재귀함수를 뜻한다.
• 하지만 수학함수 계산에만 유용한 것이 아니다.
• 자기 자신을 재 참조하는 방법을 말한다.
• 모든 recursion은 반복문으로 변경 가능하고, 그 역도 성립한다.
• recursion은 복잡한 알고리즘을 단순하고 알기 쉽게 표현하지만 함수 호출에 따른 오버헤드가 있다.

 

2. 문제풀이 시 중요한 부분

• 기저부분(base case)와 순환부분(recursive case)를 나누어 생각해야된다.
• 기저를 먼저 생각해본다.

 

 

3. 예시

• 펙토리얼 함수

#include <iostream>

using namespace std;

int fac(int n){
    if(n == 1)
        return 1;
    else
        return n * fac(n-1);
}

int main(){
    int result;
    result = fac(5);
    cout << result << endl;
}

'5!'를 출력하는 코드

 

 

• 피보나치 수열 (n번째 수열의 값 구하기)

#include <iostream>
using namespace std;

int fibo(int n){
    
    if( n < 0){ // exception
        cout << "please put positive integer" << endl;
        return -1;
    }
    
    if( n < 2 )
        return n;
    
    else
        return fibo(n-2) + fibo(n-1);
}

int main(){
    int result,n;
    cin >> n;
    
    result = fibo(n-1);
    cout << result << endl;
}

n을 입력받아 n번째 피보나치수열의 값을 출력하는 코드

 

 

 

• 두 수의 최대공약수 구하기

※ Euclid Method

 1. a≥b인 두 양의 정수 a와 b에 대해서 a가 b의 배수이면 gcd(a , b) = b이고, 그렇지 않으면 gcd(a,b) = gcd(b , a%b)
 2. gcd(a , b)   =     a            (b가 0이라면)
                 = gcd(b , a%b)     (b가 0이 아니라면)

#include <iostream>
using namespace std;

int gcd(int a, int b){
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b= tmp;
    }
    if(a % b == 0){
        return b;
    }
    else{
        return gcd(b, a%b);
    }
    
}

int main(){
    int result,a,b;
    cin >> a >> b;
    
    result = gcd(a,b);
    cout << result << endl;
}

숫자 a.b (무조건 양수라 가정) 를 입력받아 최대공약수를 출력하는 코드

 

• 문자열의 길이 계산

string을 지나가며 비어있지 않으면 1을 더하고 다음 부분을 확인

• 문자열의 프린트

길이 계산할 때 처럼 string을 지나가며 하나씩 출력.(출력 뒤에 recursion들어간다.)

• 문자열을 뒤집어 프린트

recursion으로 먼저 들어간 뒤에 출력 (앞 문자열 프린트와 반대로 출력)

 

 

 

4. 강의 내용 정리

순환의 개념과 기본 예제 1:  excelsior-cjh.tistory.com/28

Recursion의 개념과 기본 예제들

순환의 개념과 기본 예제 2: https://excelsior-cjh.tistory.com/29?category=922441

Recursion의 개념과 기본 예제들 - 2

순환의 개념과 기본 예제 3:

Recursion의 개념과 기본 예제들 - 3