Welcome, guest! We are a creative arts/general discussion community, and welcome guests and members alike to participate in our discussions. While registration is not required to post, we strongly recommend considering an account with us, as it a quick, free, and easy way to fully utilize all of the features on our forum. We hope you enjoy your stay!


Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Recursive Sequence of Death [Python]
#1
We've been working on recursive sequences in python in classes lately, and I was a little surprised at how much math actually makes a difference in your ability to optimize code. I wrote a little demonstration for one of my assignments. 

The fibonacci sequence makes no sense to me, but essentially, it goes like this. 

0, 1, 1, 2, 3, 5, 8, 13, 21, ... 

Each digit is the sum of the two previous digits. Pretty simple. We could definitely extrapolate this as far as we wanted to and get an infinitely large number of digits, but I won't go there. Apparently this is some sort of important sequence in computer science and I don't know why, but you should be able to see the pattern easily enough. 

Say we wanted to know what, say, the 20th digit in the sequence was? It turns out that the method for finding this is a little bit more complicated than you'd think. It's rather tedious to go and actually add up all of the numbers. And particularly if you're going to use a recursive sequence, as fast as we think computers are these days, trying to go past about the 40th term or so in the sequence will crash my macbook because literally going through and generating this sequence is that tedious for a computer. Maybe yours might get a tad bit higher but I'd be willing to bet you won't get past 50 in Python. 

Okay, but why in the world is this so freaking slow?

It's because it's recursive. If it wants to find the 5th number in the sequence, it first must find the 4th and the 3rd, and add those up. But because it doesn't know what the 4th and the 3rd are, in order to find the 4th, it must find the 3rd and the 2nd. And in order to find the 3rd, it must find the 2nd and the first. And it has to go through all of these steps before it can give a simple answer. Although this is easy for small numbers, as you can probably imagine, this starts to grow exponentially once you start finding, say, the 20th, or the 30th, or the 35th number in a sequence. The next thing you know, your computer can't even find the 40th term in a simple sequence without crashing, where you could probably do it by hand in a matter of a few minutes. 


There are two ways to speed this up. Instead of calling the same function over and over again and creating a gigantic tree of function calls to recalculate the same data over and over and over again, you can either save what each digit is as you go, and only calculate if you haven't saved that particular digit yet, or you can use something called an exact solution (a simple formula you make out of the recursive sequence using some sort of voodoo magic) to do the trick. By saving these numbers, it prevents the results from growing exponentially because it never has to recalculate values it's gone over before. You can easily calculate, say, the 4000th term with this method. 

I demonstrated all three methods with the following code. It calculates the 35th number in the sequence. Enough to take a few seconds on the recursive calculation, but not enough to crash my Macbook. Hopefully it won't crash yours. Tongue

Code:
import sys

sys.setrecursionlimit(2000000000)

print ("Will evaluate three methods of calculating the fibonacci sequence at 35.\n")

#define a simple recursive fibonacci sequence. 
def recursive_f(n):
    """Slow recursive function. n = the number to evaluate. """
    
    if n == 0:
        return 0     #base case
    elif n == 1:
        return 1     #another base case
    else:
        return recursive_f(n-1)+recursive_f(n-2)


#same as the previous function, but store previous values.
#this keeps the function from re-evaluating the same values. 
def mem_f(n, mem=dict()):
    """Memoization recursive method. n = num to eval. Don't pass mem. """
    
    if (n in mem):
        return mem[n]   #welp we already saved a value. Don't re-evaluate. 
    
    if n == 0:
        return 0    #base case  
    elif n == 1:
        return 1    #base case
    else:
        value = mem_f(n-1, mem)+ mem_f(n-2, mem)
        mem[n] = value  #store value
        return value


#This solution is a little different. This is a formula that is not recursive.
#In theory python shouldn't crash, but large numbers are beyond python's range.     
def fib_exact(n):
    """Calculated exact solution from second order sequence. n = num to eval."""
    
    value1 = ((1 + (5**(0.5)))**n)
    value2 = ((1 - (5**(0.5)))**n)
    value3 = (2**n) * (5**(0.5))

    result = (value1 - value2) // value3
    return int(result) 


#recursive with slow method. will take forever.
print ("Slow recursive method: ", end="")
print (str(recursive_f(35)) + "\n")

#recursive with fast method. Much faster.
print ("Fast recursive method: ", end="") 
print(str(mem_f(35)) + "\n")

#Exact solution. The fastest of them all.
print ("Exact non-recursive method: ", end="") 
print (str(fib_exact(35))) 

This will run in Python 3 if you want to save it into a .py file and run it. And I attached a file with this post too.

This page (yes that's a link) pretty much describes what we spent an hour or two doing in class to optimize this. It's my very first semester in this new program, I haven't even taken Calculus yet, and I already feel like my head is hurting. Tongue

Needless to say, you can teach yourself to program, but it's hard to teach yourself everything. I feel that, even solving simple problems, I have learned a lot.  Finna


Attached Files
.zip   fib2.py.zip (Size: 1.29 KB / Downloads: 11)
[Image: makestation_submatrix31_5.png]
Together, we can make something awesome...
Reply
Thanks given by:
#2
haha nice! python is currently my favorite language just because of it's flexibility.

have fun learning to tame the snake Big Grin
[Image: oEirbE7.png]
Reply
Thanks given by: Darth-Apple
#3
Haha thank you! Yeah Python is pretty easy all things considered. It's so nice to code that I almost wish it was more popular in the web sphere of things. As much as I don't particularly care for PHP, it's what we use here because it's what is widely supported.

Java is probably going to be what I have to tackle next, unfortunately. And Java is no fun, from what little I have done so far.
[Image: makestation_submatrix31_5.png]
Together, we can make something awesome...
Reply
Thanks given by:
#4
@Darth: ever try combining python with I3 and some Texmode User interface stuff?

if you've ever played hacknet it looks really close to the game's interface, crazy stuff Big Grin
[Image: oEirbE7.png]
Reply
Thanks given by:
#5
Hmm, that's the first I've really heard of it. I've done a fair amount of stuff in Turtle (trivially easy), might have to check it out.
[Image: makestation_submatrix31_5.png]
Together, we can make something awesome...
Reply
Thanks given by:
#6
Using python programs while running this window manager.

[Image: gnome.png]

Compare to a screenshot of this game.

[Image: ss_2e1431ffb153024cf3e0080e6c1ce7b856c76...1496621168]

crazy right?

but super hard core functional.
[Image: oEirbE7.png]
Reply
Thanks given by:




Users browsing this thread: 1 Guest(s)

Contact Us | Makestation | Return to Top | Lite (Archive) Mode | RSS Syndication
Proudly powered by MyBB 1.8, © 2002-2018 MyBB Group.
Design/theme made in house. © 2014 by Makestaton.
All rights reserved.
We also made a free chat room hosting service for communities! If you need one, check out chatcave.me.