재귀함수 알고리즘의 이해.....Fibonacci Sequence
피보나치
n =
15
번째
Running
알고리즘
f[n_]:=f[n-2]+f[n-1]
f[n_]:=f[n]=f[n-2]+f[n-1]
총 연산횟수 : 1,219 회
f[15]
f[1]
f[2]
f[3]
f[4]
f[5]
f[6]
f[7]
f[8]
f[9]
f[10]
연산횟수
233
377
233
144
89
55
34
21
13
8
f[15]
f[11]
f[12]
f[13]
f[14]
f[15]
연산횟수
5
3
2
1
1
f[15]
=
f[13]+f[14]
=
f[11]+2f[12]+f[13]
=
f[9]+3f[10]+3f[11]+f[12]
=
f[7]+4f[8]+6f[9]+4f[10]+f[11]
=
f[5]+5f[6]+10f[7]+10f[8]+5f[9]+f[10]
=
f[3]+6f[4]+15f[5]+20f[6]+15f[7]+6f[8]+f[9]
=
f[1]+7f[2]+21f[3]+35f[4]+35f[5]+21f[6]+7f[7]+f[8]
=
22f[1]+63f[2]+70f[3]+56f[4]+28f[5]+8f[6]+f[7]
=
92f[1]+189f[2]+84f[3]+36f[4]+9f[5]+f[6]
=
176f[1]+309f[2]+45f[3]+10f[4]+f[5]
=
221f[1]+364f[2]+11f[3]+f[4]
=
232f[1]+376f[2]+f[3]
=
233f[1]+377f[2]
Copyright(c) MATHOUGHT.COM Since 2000​​Jang-hoon Lee (Paju girls’ high school, mathought@gmail.com)