Recursive_Sequence

Explain

• 수열의 합을 구하기 위한 방법 정리.
• 문제 해결 시 Recursive한 해결 방법을 찾아내기 위한 노력할 것.
• Iteration, Recursion 2가지 방식으로 풀이 후 비교. 
• 문제 해결 시점에서 Iteration, Recursion 각각의 방법을 도출한 뒤 최적의 방법을 선택할 것.
• 문제마다 Iteration방식이 최적 일수도 있고 Recursion 방식이 최적일 수가 있다.

$$S(n) = \sum_{i=1}^{n}i = 1 + 2 + ... + n $$

Iteration

//Iteration method.
int S_Iteration(int n)
{
	int i;
	int sum = 0;
	
	for(i = 1; i <= n ; ++i)
	{
		sum += s + i;
	}

	return sum;
}

Recursion

$$ S(n) = \begin{cases} 0 \text{ if n <= 0 }\\ S(n-1) + n\text{ if n > 0 }\end{cases} $$

• 0과 같거나 작은경우 0
  
• 0보다 큰경우 \(S(n-1) + n\) 이 성립한다.
  

//Recursion method.
int S_Recursion(int n)
{
	if(n <= 0) return 0;
	return S_Recursion(n-1) + n;
}

Time Complexity

• Iteration : \(O(n)\)
• Resursion : \( T(n) = \begin{cases} 1 \text{ if n <= 0 }\\ T(n-1) + n \text{ if n > 0 } \end{cases} \) 
• 0과 같거나 작을경우 \(T(n) = 1\) 
• 0보다 클경우 \(T(n) = T(n-1) + 1\)

Reference

• Wiki - 수열
  
• Wiki - Big O notation