순환(Recursion)의 개념과 기본 예제1

---

순환 함수란 무엇이며, 무한 루프에 빠지지 않으려면 어떤 경우가 존재해야 하는지
그리고 수학적 귀납법에 대해 알아봅시다.

본 포스팅은
<인프런 - 권오흠 강사님의 영리한 프로그래밍을 위한 알고리즘 강좌 > 자료를 인용하였음을 알려드립니다.

---

순환이란?

recursion은 항상 무한루프에 빠질까?

// 1 ~ n까지의 합을 구한다.
int main() {
    int result = func(4);
}

int func(int n) {
    if (n == 0) {
        return 0;
    }
    else {
        return n + func(n-1);
    }
}

무한루프에 빠지지 않으려면? & recursion의 해석

// 이 함수의 mission은 0 ~ n까지의 합을 구하는 것이다.
int func(int n) {
    // Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
    // n = 0이라면, 합은 0이다.
    if (n == 0)
    return 0;
    else
    // Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.
    // n이 0보다 크다면,
    //  0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.
    return n + func(n-1);
}

순환함수와 수학적 귀납법

정리: 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까지의 합을 올바로 계산하여 반환한다.

package lec00.algorithm;

public class Alg02 {
	public static void main(String[] args) {
		int n = 4;
		func(n);
	}
	public static void func(int k) {
		if (k <= 0)
			return;
// Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
		else {
			System.out.println("Hello...");
			func(k-1);
// Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.
		}
	}
}
// recursion이 항상 무한루프에 빠지는 것은 아니다.

package lec00.algorithm;

// 1 ~ n까지의 합을 구한다.
public class Alg03 {
	public static void main(String[] args) {
		int result = func(4);
		System.out.println(result);
	}

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

}

---

Factorial: n!

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!을 반환한다.

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