순환(Recursion)에 대해(1)

순환

- 자기 자신을 다시 호출하는 함수를 말한다.

void func(~) {

~

func(~);

~

}

ex)

public class Ex1 {

public static void main (String[] args) {

func();

}

public static void func() {

System.out.println("Hello!");

func();

}

}

-> 자신을 계속 반복하여 호출하게 되면 무한정 자신을 호출하는 무한 반복에 빠지게 된다.

- 순환은 코드의 작성법에 따라 무한루프에 빠지지 않게 만들 수 있다.

1) Base case : 무한반복에 빠지지 않게 하는 조건식이 적어도 하나는 존재해야 한다.

2) Recursive case : 순환을 계속 하다보면 결국 base case에 수렴할 수 있도록 해야 한다.

ex)

public class Ex2 {

public static void main (String[] args) {

int n = 4;

func(n);

}

public static void func(int num) {

if (num <= 0)

return; //Base case

else {

System.out.println("Hello!");

func(num - 1); //Recursive case

}

}

}

-> num이 0에 도달하게 되면 함수 호출을 멈추게 되어 입력된 수만큼만 반복을 수행하며 무한반복에 빠지지 않을 수 있다.

ex)

public class Ex3 {

public static void main (String[] args) {

int result = func(4);

}

public static int func (int n) {

if (n == 0)

return 0; //func(0)일 경우 0이 반환된다.

else

return n + func(n - 1); //n이 0보다 크다면 n까지의 합은 0에서 n - 1까지의 합에 n을 더한 것이라는 뜻이다.

}

}

-> 위 코드는 0부터 n까지의 합 계산을 수행하게 된다. func(4)라는 것은 4까지 더하라는 것이며 10의 결과를 반환한다.

Ex3에 대한 수학적 귀납법

- 가정 : func(int n)은 음이 아닌 정수 n에 대해서 0부터 n까지의 합을 올바로 계산한다.

- 증명

1) n = 0인 경우 : n = 0일 때 0을 반환한다.

2) 임의의 양의 정수 k에 대해 n < k일 때 0부터 n까지 합을 올바르게 계산후 반환한다 가정한다.

3) n = k일 경우 func은 먼저 func(k - 1)을 호출한다. 이 때 2번의 가정에 의해 0부터 k - 1까지의 합이 올바르게 계산되어 반환된다. 메소드 func은 해당 값에 n을 더한 후 반환한다. 따라서 func은 0부터 k까지의 합을 올바로 계산한 후 반환한다 할 수 있다.

Factorial : n!

- 0! = 1

- n! = n x (n - 1) (n > 0일 때)

- 구현

public static int factorial (int n) {

if (n == 0)

return 1;

else

return n * factorial(n - 1);

}

팩토리얼에 대한 수학적 귀납법

- 가정 : factorial (int n)은 음이 아닌 정수 n에 대해서 n!을 올바로 계산한다.

- 증명

1) n = 0일 경우 : n = 0일 때 1을 반환한다.

2) 임의의 양의 정수 k에 대해 n < k일 경우 n!이 올바르게 계산된다 가정한다.

3) n = k일 때 factorial은 먼저 factorial(k -1)을 호출하고 2번의 가정에 의해 (k - 1)!이 올바르게 계산되어 반환된다. 이 결과에 더해 factorial메소드는 k * (k - 1) = k!을 반환하게 된다.

$x^n$

- x에 대한 n제곱 계산식이다.

- x^0 = 1

- x^n = x * x^n-1 (n > 0일 때)

- 구현

public static duoble power (double x, int n) {

if (n == 0)

return 1;

else

return n * power(x, n - 1);

}

피보나치 수(Fibonacci Number)

- $f_0$ = 0

- $f_1$ = 1

- $f_n$ = $f_{n-1}$ + $f_{n-2}$ (n > 1일 때)

- 구현

public static int fibonacci (int n) {

if (n < 2)

return n;

else

return fibonacci(n - 1) + fibonacci(n - 2);

}

최대 공약수 알고리즘 (Euclid Method)

- m >= n인 두 양의 정수 m과 n에 대해 m이 n의 배수이면 gcd(m, n) = n이고, 그렇지 않으면 gcd(m, n) = gcd(n, m % n)이다.

- 조건

n = 0일 경우 최대공약수는 m이다.

그렇지 않으면 gcd(n, m % n)메소드를 실행한다.

- 구현

public static double gcd (int m, int n) {

if (n == 0)

return m;

else

return gcd(n, m % n);

}