[순환] Recursion의 개념과 기본 예제

Recursion
자기 자신을 호출하는 함수
재귀 함수

Recursion의 기본 개념

void func(int k) {
    if (k <= 0) //Base Case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
        return;
    else { //Recursive case : recursion을 수행하다보면 결국 base case로 수렴해야 한다.
        printf("Hello...");
        func(k - 1);
    }
}
int main(void) //메인 함수
{
    int n = 4;
    func(n);
}

 

Recursion의 해석

//이 함수의 미션은 0~n까지의 합을 구하는 것이다.
int func(int n) {
    if (n == 0) //n=0이라면 합은 0이다.
        return 0;
    else
        return n + func(n - 1); //n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.
}

수학적 귀납법과 동일

 

Factorial을 Recursion으로 정의해보자

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

 

x^n을 Recursion으로 정의해보자

int doublePower(double x, int n) {
    if (n == 0) 
        return 1;
    else
        return x*doublePower(x, n-1);
}

 

피보나치(Fibonacci)를 Recursion으로 정의해보자

1번째 피보나치 수: 1
2번째 피보나치 수: 1     //fib(1) + fib(0)
3번째 피보나치 수: 2     //fib(2) + fib(1)
4번째 피보나치 수: 3     
5번째 피보나치 수: 5   
.
.
값
fib(0)=0
fib(1)=1
fib(2)=1
fib(3) = fib(2) + fib(1) = 1 + 1 = 2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int fibonacci(int n) {
    if (n < 2) 
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}
int main(void) 
{
    int n;
    scanf("%d", &n);
    printf("%d번째 피보나치 수는 %d입니다.\n", n, fibonacci(n));
    return 0;
}

 

최대공약수(Euclid Method)를 Recursion으로 정의해보자

m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gdc(m,n)=n이고,
그렇지 않으면 gdc(m,n)=gcd(n,m%n)이다.
cf) gcd(n,m%n) == n과 m을n으로 나눈 나머지 사이의 최대공약수

int gdc(int m, int n) { //m > n
    if (m < n) {
        int tmp = m; m = n; n = tmp; //swap m and n
    }
    if (m % n == 0)
        return n;
    else
        return gdc(n, m % n);
}

int gcd(int p, int q) { //단순한 버전, p가 q보다 클 필요가 없다
    if (q == 0)
        return p;
    else
        return gcd(q, p % q);
}

위의 함수가 무한루프에 빠지지 않는 이유는??
생각해보자.
case1: p=16, q=32
return gcd(32,16)
return gcd(16,0)
return 16
case2: p=32, q=16
return gcd(16,0)
return 16
case3: p=14, q=21
return gcd(21,14)
return gcd(14,7)
return gcd(7,0)
return 7
이게되네 이왜진

 

[무료] 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 강의