This program calculates Fibonacci numbers using recursion. The Fibonacci sequence is defined by the next number in the sequence being the sum of the previous 2 numbers with the 0th number being 0, and the first number being 1. Fib(0) = 0 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2) # (for n > 1) Examples: Fib(2) = Fib(0) + Fib(1) = 0 + 1 = 1 Fib(3) = Fib(1) + Fib(2) = 1 + 1 = 2 Fib(4) = Fib(2) + Fib(3) = 2 + 1 = 3 and So on. This program uses a recursive structure because I wanted to see if it could be done in scratch. since all of scratch's variables are global, you need to use a stack in order for recursion to work properly. The program also uses Dynamic programming to optimize the algorithm by storing previous results for later use in a cache so the program doesn't need to calculate them again. This greatly increases the speed of the program
#fibonacci #recursion #dynamic_programming If you are curious on how the project works, please click "See Inside". :-) I tried to explain how the code works!
