[Data Structure] 2. 순환

rany·2020년 6월 2일
0

자료구조

목록 보기
2/4
post-thumbnail

Recursion(순환)

정의

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

프로그램이 뇌절한다고 생각하면 쉽다 😁

순환 알고리즘의 구조

  1. 자기 자신을 순환적으로 호출하는 부분
  2. 순환 호출을 멈추는 부분

아래는 순환을 이용한 팩토리얼 계산 코드이다.

int factorial (int n) {
    if (n <= 1) {
     	return 1;
    } else {
    	return (n * factorial(n-1));
    }
}

여기서 if 문은 순환을 멈추는 부분이고 else 에서 계속 순환 호출을 하는 것이다.

순환 호출이 되면 컴퓨터 내부에서는..

순환 또한 프로그램에서 일반적인 다른 함수의 호출과 동일하다. 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라고 하는데, 호출된 함수가 끝나면 시스템 스택에서 복귀주소를 추출하여 호출한 함수로 돌아간다. 순환 호출이 계속 중첩될수록 시스템 스택에는 활성 레코드들이 쌓이게 되는 구조이다.

순환의 원리

문제의 일부를 해결한 다음, 나머지 문제에 대하여 순환 호출을 한다는 것.
이런 식으로 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할 정복(Divide and Conquer)라고 한다. 즉, 순환이 일어날 때마다 문제의 크기가 작아진다는 것.

장점과 단점

장점

  • 이해하기 쉽다.
  • 쉽게 프로그래밍할 수 있다.

단점

  • 프로그램 실행 시간과 메모리 사용에 있어서 비효율적이다. (순환 호출이 일어날 때마다 호출하는 함수의 상태를 기억해야 하므로 메모리를 더 필요로 함)

나는 순환(recursion)보다 반복(iteration)으로 표현하는게 더 익숙한데.. 아마도 순환을 잘 안 써봐서 그런가보다.

profile
컴퓨터는 나의 베프

0개의 댓글