def fibonacci(n):
answer = [0,1] #list의 초기값을 0,1로 지정
for i in range(2,n+1):#i= list의 주소를 뜻함
answer.append(answer[i-1]+answer[i-2])#list에 추가
#print(answer) # 피보나치 list를 출력위해
#print(i) #리스트 주소가 잘 돌고있는지 확인
return answer[-1] #리스트에서 가장 마지막것만 출력해줌
$print(fibonacci(30))
832040
초기에 python으로 해결하려 하였으나 실패ㅜㅜ 시간 계산 함수가 따로있다고 하는데 조금 더 찾아보고싶었지만 노타임.. 노열정..
<python 으로 반복문 사용하여 피보나치 계산> -> 아 잘되는데 시간 계산 .....
<java 피보나치 합 /시간 계산>
import java.util.Scanner;
public class recursionVsIteration {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//원하는 숫자 입력
System.out.print("Enter the last element of Fibonacci sequence: ");
long n = sc.nextInt();
//반복문 출력
System.out.println("Fibonacci iteration:");
long start = System.currentTimeMillis();
System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibIteration(n));
System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
//재귀함수 출력
System.out.println("Fibonacci recursion:");
start = System.currentTimeMillis();
System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibRecursion(n));
System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
}
//반복문 method
static long fibIteration(long n) {
long x = 0, y = 1, z = 1;
for (long i = 0; i < n; i++) {
x = y;
y = z;
z = x + y;
}
return x;
}
//재귀 method
static long fibRecursion(long n) {
if ((n == 1) || (n == 0)) {
return n;
}
return fibRecursion(n - 1) + fi
<피보나치 수열>
1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
<피보나치 수열의 호출 방법>
1. 재귀 호출
-함수 호출 횟수가 너무 큼 -> 해결책 : recursive를 한겹만 쓰면 확실히 줄어들 것
-stack 깊이가 너무 깊어져서 컴퓨터 터짐..(stack overhead)-> 해결책 : stack을 쓰되 새로 만들지말고 누적해서 재사용하자
-대신 적은 코드 사용해 효율적으로 처리 -> 종료하는 지점 정의해줬을 때 얘기이다..
2. 반복 호출
- 반복 할 때마다 나온 계산 값을 어딘가에 저장해 두고 그 다음 반복에서는 앞 단계에서 저장된 값에 새로운 값 내용 누적 시킨다.
- 매개변수 리스트 보관(메모리 영역) / 메소드 실행공간(복사 공간) 필요하다
3. 꼬리 재귀(tail-recursion)
-재귀가 느려지는 이유(작업 끝마쳐도 해야할 일 남아)를 보완해서 함수의 꼬리 부분에 호출하여 원래 시점으로 돌아갔을 때 해야할 일 이 없게 만드는 호출
