⚡ Stack 응용과 재귀호출

📌 Stack 응용

🔷 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.

• 문자열 수식 계산의 일반적 방법
  1) 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용)
  2) 후위 표기법의 수식을 스택을 이용하여 계산한다.

  💡 중위 표기법(infix notation)
  연산자를 피연산자의 가운데 표기하는 방법 ex) A + B

  💡 후위 표기법(postfix notation)
  연산자를 피연산자 뒤에 표기하는 방법 ex) AB+

🔷 중위표기식의 후위표기식 변환 방법 1
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동
3) 괄호를 제거

🔷 중위표기식의 후위표기식 변환 방법 2 (스택 이용)
1) 입력 받은 중위 표기식에서 토큰 읽기
2) 토큰이 피연산자이면 토큰 출력
3) 토큰이 연산자(괄호포함)일 때, 이 토큰이 스택의 top에 저장되어있는 연산자보다 우선순위가 높으면 스택에 push, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자를 push한다. 만약 top에 연산자가 없으면 push
4) 토큰이 오른쪽 괄호 ')'이면 스택 top에 왼쪽 괄호 '('가 올 때 까지 스택에 pop 연산을 수행하고 pop한 연산자를 출력. 왼쪽 괄호를 만나면 pop만 하고 출력은 하지 않는다.
5) 중위 표기식에 더 읽을 것이 없다면 중지하고, 더 읽을 것이 있다면 1부터 다시 반복
6) 스택에 남아 있는 연산자를 모두 pop하여 출력

❗ 스택 밖의 왼쪽 괄호는 우선 순위가 가장 높으며, 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮다.

🔷 후위 표기법의 수식을 스택을 이용하여 계산
1) 피연산자를 만나면 스택에 push
2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push
3) 수식이 끝나면, 마지막으로 스택을 pop하여 출력

📌 재귀 호출

🔷 자기 자신을 호출하여 순환 수행되는 것

• 함수 호출은 메모리 구조에서 스택을 사용한다. (❗ 이름만 같은 다른 메서드)

  ❗ 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능저하가 발생한다.

• 일반적으로 기본 부분(Base Case), 재귀 부분(Recursive case)로 구성된다.
  • Base case: 재귀 호출에서 빠져 나가기 위한 조건
  • Recursive case: 자신을 호출하는 부분(Base case로 유도)
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.

public class dailyClass {
	public static int cnt = 0;
	
	public static void main(String[] args) {
		func1(); // StackOverflow
		func2(10);
	}
	
	public static void func1 () {
		cnt++;
		System.out.println(cnt);
		func1();
	}
	
	// 재귀 함수는 두 부분으로 작성하는 경우가 많다.
	public static void func2 (int num) {
		// 1. 기본 파트: 재귀 함수를 종료하는 조건을 작성하는 부분
		if(num == 0) {
			return;
		} 
		// 2. 재귀 파트: 나 자신을(자신처럼 보이는) 다시 호출하는 부분
		System.out.println(num + " 함수호출");
		func2(num - 1);
		System.out.println(num + " 함수리턴");		
	}
}

// 팩토리얼 예제
public class dailyClass {
	public static void main(String[] args) {
		System.out.println(fact(10)); // 3628800
	}
	
	public static int fact (int num) {
		// 1. 기본 파트: 재귀 함수를 종료하는 조건을 작성하는 부분
		if(num == 1) {
			return 1;
		} 
		// 2. 재귀 파트: 나 자신을(자신처럼 보이는) 다시 호출하는 부분
		return num * fact(num - 1);		
	}
}

// 피보나치 예제
public class dailyClass {
	public static void main(String[] args) {
		System.out.println(fib(10)); // 3628800
	}
	
	public static int fib (int num) {
		// 1. 기본 파트: 재귀 함수를 종료하는 조건을 작성하는 부분
		if(num<=1) return num;
		// 2. 재귀 파트: 나 자신을(자신처럼 보이는) 다시 호출하는 부분
		return fib(num-1) + fib(num-2);		
	}
}

❗ 피보나치를 재귀함수로 구현하면 엄청난 중복 호출이 존재한다.
=> 상당히 느려진다.
=> 이런 경우를 방지하기 위해 메모를 이용한다.

public class dailyClass {
	public static void main(String[] args) {
		System.out.println(fib2(45));
	}
	
	// 기록
	public static int[] memo = new int [50];
	// static 블록으로 memo[0] = 0; memo[1] = 1; 초기화
	static {
		memo[0] = 0;
		memo[1] = 1;
	}
	
	public static int fib2 (int num) {
		if(num >= 2 && memo[num] == 0) {
			memo[num] = fib2(num-1) + fib2(num-2);
		}
		
		return memo[num];
	}
}

💡 재귀 함수가 종료할 수만 있다면 굳이 기본 파트를 분리하여 구현할 필요는 없다.