[C language] [Swift] 알고리즘 | 재귀함수 (fibonacci 피보나치 수열)

(이건 친구가 물어본 문제인데.. 아... 코드 노트북에 있는데 다른 노트북에 있다......!)

 

우선, 피보나치 수열은,

위키백과의 피보나치 수열 설명글.

이렇다. 이게 피보나치 수열이다.

0, 1, 1, 2, 3, 5, 8, ..... 이라고 하고 문제를 풀도록 하겠다.

 

우선 C 로 구현하면, 

이렇다.

 

fibo_rec(3)에서 

return fibo_rec(2)+fibo_rec(1)이고, fibo_rec(1)은 1 자기 자신을 return 하므로 1이다.

fibo_rec(2)는

return fibo_rec(1)+fibo_rec(0)이다. 둘 다 자기 자신을 return 한다. 

 

따라서 fibo_rec(3)은

return			fibo_rec(2)			+	fibo_rec(1)
			= fibo_rec(1)	+	fibo_rec(0)		=1
			=1	+	0
			=1	+	0	+	1

1 + 0 + 1 = 2가 된다.

 

Swift 표현으로 바꾸면, 

 

근데 왜 for문으로 만든게 에러난다.

(4) 넣으면 3 나와야 되는데 4가 나온다.

 

-> 알았다. ... 

for문에서 f2=result; 를 하고 f1=f2; 를 했다..

f1=f2; f2=result;를 해야지....... 

 

the-brain-of-sic2.tistory.com/33?category=779572

[스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리

이 블로그에서는 for 와 recursive의 복잡도 까지 다룬다. 

recursive가 코드는 짧지만 수행 속도는 더 느리다고 한다. 

수행 속도, 그리고 왜 느린지는 저 위의 블로그에서 트리를 그리면서 설명해준다.