순환 알고리즘

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

반복과 순환

  기본적으로 반복과 순환은 문제 해결 능력이 같으며 대부분의 경우 순환 알고리즘과 반복 알고리즘은 서로 대체될 수 있다. 특히 순환 호출이 끝에서 이뤄지는 것을 꼬리 순환(tail recursion)이라 하는데, 이를 반복 알고리즘으로 쉽게 대체할 수 있다. 대부분의 언어가 순환을 지원하지만 FORTRAN, COBOL과 같은 고전적인 언어에서는 지역변수가 없거나 있더라도 정적으로 할당되므로 순환이 불가능하다. (함수 호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수 없어 순환 호출이 불가능하다.)

• 반복(iteration) : 반복 구조로 되풀이하는 방법
• 순환(recursion) : 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법
  - 특정 문제에서 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.
  - 함수호출을 하게 되므로 대부분 반복에 비해 수행 속도가 떨어진다.
  - 알고리즘의 정의가 순환적으로 되어있는 경우 유용함
    ex) 팩토리얼, 피보나치 수열, 이항 계수 계산, 이진트리 알고리즘, 이진 탐색, 하노이 탑 등

   순환의 원리 : 문제의 일부를 해결한 다음 나머지 문제에 대하여 순환 호출을 한다.

    분할정복(divide and conquer)  : 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법 

 

 

 

순환의 종류

1. 머리 순환(head recursion) : 순환 호출이 순환 함수 처음에서 이뤄지는 경우
2. 꼬리 순환(tail recursion) : 순환 호출이 순환 함수 맨 끝에서 이뤄지는 경우 → 반복문으로 쉽게 변환 가능
3. multi recursion : 여러 군데에서 자기 자신을 호출하는 경우

 

 

 

순환 호출 과정

1. 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 
    활성 레코드(activation record)  : 함수를 위한 시스템 스택에서의 공간
2. 준비가 끝나면 호출된 함수의 시작 위치로 점프하여 수행 시작
3. 호출된 함수가 끝나면 시스템 스택에서 복귀 주소를 추출하여 호출한 함수로 되돌아감

 

 

 

순환 알고리즘의 구조

[반환형] [함수이름] (매개변수)
{
    if (종료조건)
    {
    	// 순환을 멈추는 부분
    }
    else
    {
    	// 순환호출 하는 부분
    }
}

종료 조건이 없으면 무한히 반복하게 되므로 주의한다.

 

 

순환 알고리즘 문제

• 팩토리얼(거듭제곱) : https://pridiot.tistory.com/260
• 피보나치
• 하노이의 탑