th42500의 TIL

피보나치 수열 이란? 👉 0(0항)과 1(1항)로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열 피보나치 수열 함수 피보나치 수열의 i번 째 값을 계산하는 함수 F 👉 F0 = 0, F1 = 1 👉 Fi = Fi-1 + Fi-2 (단, i >= 2 일 때) 피보나치 수를 구하는 재귀함수 위의 정의를 이용하여 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현 가능 fibo(n) IF n < 2 : RETURN n ELSE : RETURN fibo(n-1) + fibo(n - 2) 이 때 fibo(n)는 n항을 구하는 메소드(함수) 피보나치 수열을 구했을 때 문제점 피보나치를 재귀로 구현하였을 때 문제점은 매우 많은 중복 호출이 존재한다는 점 그렇다면 중복을 피할 수 있는 방법은 없을까? 이..