재귀 함수를 이용한 피보나치 수열 프로그램

재귀함수를 이용하면 더 간단하게 이렇게 프로그램을 작성할 수가 있다

​

하지만, 재귀함수의 문제점은 수가 커질수록 연산해야하는 횟수가 기하급수적으로 많아진다는것이다.

​

예를들어 피보나치 함수에 50을 넣어보자

​

컴퓨터는 49, 48로 나누고 다시 48,47, 47, 46으로 나누고 계속 해서 나눌것이다

​

따라서 2^50 개의 연산을 해야하는데 실행해보면 너무나도 많은 연산을 처리하느라

​

결과가 나오지 않는것을 알 수 있다.

​

2^1000 인 경우는 말할 필요도 없다

​

​

따라서 재귀함수는 때에따라서는 간결하게 코드를 작성하는데 도움이 되지만

​

더욱 더 많은 시간을 소비 할 수가 있다