점화식이란 무엇인가?

점화식이란?

수학에서 점화식(漸化式) 또는 재귀식(再歸式, 영어: recurrence relation)이란 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식이다.

 

프로그래밍에서 어떤 함수 안에서 자기 자신을 다시 호출하는 함수를 재귀함수라고 한다. 이때 호출하는 함수 그 자체와 재귀적으로 호출되는 함수 사이에는 어떤 상관관계가 있기 마련이다. 아래의 점화식은 이웃하는 두 개의 항 사이에 성립하는 관계에 대한 것을 말하고 있다.

 

 

an과 an + 1이 인접한 항이라고 할 때, 어떤 함수를 an에 씌워 an +1 이라는 결과를 얻을 수 있다면 함수 f가 수열 {an}의 점화식이 된다.

 

피보나치수열을 만들 때의 재귀식을 간단히 하면 다음과 같다.

 

function fibonacci(n) {
  if ( n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

 

이때 if 내용을 제외한 fibonacci(n - 1) + fibonacci(n - 2)가 바로 피보나치수열에 대한 점화식이 된다.

 

하노이의 탑 문제도 점화식으로 간단하게 정리해 둔 내용을 확인할 수 있다.

 

n 개의 원판을 이동하는 회수를 수열 an으로 정의하자. n 개의 원판을 이동시키기 위해서는 그 위쪽 n - 1개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 n - 1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알 수 있다.

 

 

 

5개의 원판을 옮겨야 한다면 위에부터 4개의 원판을 두 번째 막대로 이동하고 맨 마지막 원판을 세 번째 막대로 이동한다. (+ 1) 그리고 두 번째 막대에 있는 4개의 원판을 모두 세 번째 막대로 이동하면 된다.

 

함께 읽으면 좋은 글

[프로그래머스 Programmers] 피보나치 수

지구 종말에 대한 하노이 예언

[하노이탑의 최소 횟수 구하는 방법]-점화식 이용하기

 

참고 사이트

점화식 (TIL 42일차)