[알고리즘][Recursion] 재귀(Recursion) 기본 개념과 예제 1

Recursion

---

재귀(Recursion)란 자기 자신을 호출하는 함수를 의미한다.

void func(...)
{
	...
    func(...);
    ...
}

 

하지만 아래와 같이 recursion은 무한루프에 갇힐 수 있다.

public static void func()
{
	System.out.println("hello func!");
	func();
}

hello func!
hello func!
hello func!
hello func!
...
...

 

Recursion이 항상 무한루프에 빠지지는 않는다. Recursion이 적절한 구조를 가지고 있다면 무한루프에 빠지지 않는다.

• Base Case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
• Recursive Case : recursion을 반복하다보면 결국 base case로 수렴해야 한다.

예제1 - 0~n까지의 합계 구하기

// 0~n까지의 합계를 재귀적으로 구함
public static int func(int n)
{
	if(n==0)	// base case : n==0
	{
		return 0;
	}
	return n + func(n-1);	// recursive case : n>0
}

	// 0~n까지의 합을 구함
	@Test
	void sumTest() {
		System.out.println("sum Test");
		System.out.println(Main.func(5));
	}

15

 

recursion의 해석

• 이 함수의 목적은 0~n까지의 합을 구하는 것
• n==0이라면 합은 0
• n이 0보다 크다면 0~n까지의 합은 0에서 n-1까지의 합에 n을 더한 것

순환함수와 수확적 귀납법

• 정리
  • func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바르게 계산
• 증명
  1. n=0인 경우: 0을 반환한다. 올바르다.
  2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정
  3. n=k인 경우 : func은 먼저 func(k-1)를 호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바르게 계산되어 반환된다. 메서드 func은 그 값에 n을 더해서 반환하므로 결국 0에서 k까지의 합을 올바르게 계산하여 반환한다

 

Factorial: n!

---

• 0! = 1
• n! = n * (n-1)! (n>0)

	// n! 값을 재귀적으로 구함
	public static int factorial(int n)
	{
		if(n==0)
		{
			return 1;
		}
		return n * factorial(n-1);
	}

	// n! 값을 구함
	@Test
	void factorialTest() {
		System.out.println("factorial Test");
		System.out.println(Main.factorial(5));
	}

120

 

순환함수와 수학적귀납법

• 정리
  • factorial(int n)은 음이 아닌 정수 n에 대해서 n!을 올바르게 계산한다.
• 증명
  1. n=0인 경우: 1을 반환한다. 올바르다.
  2. 임의의 양의 정수 k에 대해서 n<k인 경우 n!을 올바르게 계산한다고 가정하자.
  3. n=k인 경우를 고려해보자. factorial은 먼저 factorial(k-1)을 호출하는데 2번의 가정에 의해서 (k-1)!이 올바르게 계산되어 반환된다. 따라서 메서드 factorial은 k*(k-1)!=k!을 반환한다.

 

Xⁿ

---

• x^0=1
• x^n=x∗x^(n-1) if n>0

	// x^n 값을 재귀적으로 구함
	public static double power(double x, int n)
	{
		if(n==0)
		{
			return 1;
		}
		return x * power(x,n-1);
	}

	// x^n 값을 구함
	@Test
	void powerTest() {
		System.out.println("powerTest");
		System.out.println(Main.power(2, 5));
	}

32

 

Fibonacci Number

---

 

Fibonacci numbers는 제 0항을 0, 제 1항을 1로 두고 두번째 항부터는 바로 앞의 두수를 더한 수열입니다.

0 1 1 2 3 5 8 13 ...

• f_0 = 0
• f_1 = 1
• f_n = f_n-1 + f_n-2, n>1

	// n번째의 피보나치 수를 구함
	public static int fibo(int n)
	{
		if(n<2)
		{
			return n;
		}
		return fibo(n-1) + fibo(n-2);			
	}

	// n번째 피보나치 수를 구함
	@Test
	void fibonaciTest() {
		System.out.println("fibonaci Test");
		System.out.println(Main.fibo(6));
	}

8

 

최대공약수: Euclid Method

---

• m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n이다.
• m이 n의 배수가 아니면 gcd(m,n)=gcd(n,m%n)이다.

	public static double gcd1(int m, int n)
	{
		if(m<n) 
		{
			int tmp = m;
			m = n;
			n = tmp;
		}
		if(m%n==0)
		{
			return n;
		}
		else
		{
			return gcd(n, m%n);
		}
	}

	@Test
	void gcd1Test() {
		System.out.println("gcd1 Test");
		System.out.println(Main.gcd1(6, 3));
	}

3.0

 

Euclid Method : 좀 더 단순한 버전

• gcd(p,q)
  • if q=0 then p
  • otherwise gcd(q, p%q)

	// p, q의 최대 공약수를 구함
	public static int gcd(int p, int q)
	{
		if(q==0)
		{
			return p;
		}
		return gcd(q, p%q);
	}

	// p, q의 최대공약수를 구함
	@Test
	void gcdTest() {
		System.out.println("gcd Test");
		System.out.println(Main.gcd(2, 3));
	}

1

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌