[알고리즘] 재귀 알고리즘

▶ 재귀 문제를 풀 때 생각의 흐름 

1. 반복되는 작업을 찾는다 (반복되는 부분은 재귀함수나 반복문으로 해결할수 있다)
2. 반복되는 작업을 함수로 생각하고 input과 output의 형식을 각각 정한다 (output이 있을 경우 이 output이 다음번 input으로 사용될 수 있다)
3. input은 한단계씩 점진적으로 변한다 (보통 크기나 길이가 줄어든다)
4. 종료 조건을 설정한다

 

▶ 재귀 문제 TIP

1. 문제의 정의를 명확히 표기한다 (ex. 피보나치 수열이란 어떤 수열의 항 = 앞의 두항의 합)

2. 종료조건을 정확히 설정한다 

3. 재귀는 목적만 설정해주는 디클래러티브적 프로그래밍 (선언적 프로그래밍) 을 해야한다는것을 인지하자

4. 내가 생각한 컴퓨터가 알아서 슈슉 돌리고 결과를 짠하고 보여주는것은 불가능함 저장할 공간이 필요함!!

5. 재귀를 사용한 곳의 앞부분과 뒷부분은 천지 차이이다 앞부분은 재귀함수가 발동되면서 실행 되지만 뒷부분은 재귀 함수가 모두 발동한 후에 한꺼번에 실행된다 -> 재귀함수 앞, 뒤로 실행이 달라짐

 

 

▶ 재귀함수 결과는 스택구조로 저장된다 (호출의 흐름을 따라가는 방식이 다름)

 

재귀 호출이 이루어지는 라인이 종료조건에 도달하는 순간까지 그 다음 라인은 실행 되지 않는다