일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 큐
- 암호수학
- System
- 파이썬
- 백준
- 미로 탐색 알고리즘
- ftz level13
- OSI
- 파일 시스템
- windosw 문자열
- 정렬 알고리즘
- pwnable.kr
- level13
- HTML
- 자료구조
- PHP
- War Game
- SWiFT
- LoB
- Stack
- 시간복잡도
- web
- Java
- 스택
- 두근두근 자료구조
- c언어
- 재귀
- C
- windosws wbcs
- ftz
Archives
- Today
- Total
나의 기록, 현진록
[Swift] Data Structure Recursion / Fibonacci / 자료구조 재귀, 순환 / 피보나치 수열 본문
Programming/Algorithm & Data Structure
[Swift] Data Structure Recursion / Fibonacci / 자료구조 재귀, 순환 / 피보나치 수열
guswlsdk 2021. 7. 7. 10:18반응형
재귀 호출로 구현할 수 있는 가장 대표적인 예 중 하나가 피보나치 수열이다.
앞의 두 개의 숫자를 더해 뒤의 숫자를 만들면 된다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89....
func fib(_ n: Int) -> Int{
if n == 0{
return 0
}
else if n == 1{
return 1
}
else{
return fib(n-1) + fib(n-2)
}
}
이 함수는 단순하고 이해하기 쉽게 재귀 호출로 구현되었지만 사실 매우 비효율적이다. 그 이유는 무엇일까?
fib(6)이 호출하면 fib(4)가 두 번 반복하여 호출된다.
fib(6)
= fib(4) + fib(5)
= fib(2)+fib(3) + fib(3)+fib(4)
= fib(0)+fib(1) + fib(1)+fib(2) + fib(1) + fib(2) + fib(2)+ fib(3)
= fib(0)+fib(1) + fib(1)+fib(0)+fib(1) + fib(1) + fib(0) + fib(1) +fib(0) + fib(1)+ fib(1) + fib(2)
= fib(0)+fib(1) + fib(1)+fib(0)+fib(1) + fib(1) + fib(0) + fib(1) +fib(0) + fib(1)+ fib(1) + fib(0) + fib(1)
트리 구조로 시각화해야 이해하기 쉽지만 ..... 대충....
이런 현상은 재귀 호출이 깊어질수록 점점 심해질 것이도 상당히 비효율적이다. 이러한 현상의 근본적인 이유는 중간에 계산된 값을 기억하지 않고 다시 계산하기 때문이다.
해결 방안으로는 메모이제이션이라고 하는 기법이다. 다음에 Araboza
반응형
'Programming > Algorithm & Data Structure' 카테고리의 다른 글
[Swift] 백준 10829 이진수 변환 / 재귀 /recursion (0) | 2021.07.22 |
---|---|
[Swift] Data Structure recursion / hanoi / 자료구조 순환, 재귀 / 하노이 탑 (0) | 2021.07.08 |
[Swift] Data Structure divide and conquer, D&C / power / 자료구조 분할정복 / 거듭제곱 계산 (0) | 2021.07.06 |
[Swift] Data Structure recursion / divide and conquer, D&C / 자료구조 순환, 재귀 / 분할정복 (0) | 2021.07.06 |
[Swift] 백준 1012 유기농 배추 / DFS (0) | 2021.06.30 |