Shop OBEX P1 Docs P2 Docs Learn Events
Recursion Works — Parallax Forums

Recursion Works

Jon WilliamsJon Williams Posts: 6,491
edited 2006-03-31 20:45 in Propeller 1
Advanced programmers may be wondering if Spin methods are recursive -- at least with this program, the answer is yes.

attachment.php?attachmentid=40992

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon Williams
Applications Engineer, Parallax
spin_recursion.jpg
595 x 800 - 175K

Comments

  • Kaos KiddKaos Kidd Posts: 614
    edited 2006-03-29 14:22
    Wouldn't memory be the determining issue as to how deep the recursion goes?

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Just tossing my two bits worth into the bit bucket


    KK
    ·
  • Paul BakerPaul Baker Posts: 6,351
    edited 2006-03-29 14:36
    Yes but when spawning a Spin cog, one of it's arguments is a pointer to a stack, which you specify the size of. Thats why recusion works in spin, the use of a stack makes the code re-entrant. Assembler doesn't natively use stacks, to do recursive programming in assembler you would have to write your own stack routines and use them for jmpret locations.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    ·1+1=10
  • Jon WilliamsJon Williams Posts: 6,491
    edited 2006-03-29 14:53
    And this demo is running in Cog 0, so it I believe it's got the entire global RAM (about 7800 longs) to use as a stack.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Jon Williams
    Applications Engineer, Parallax
  • Paul BakerPaul Baker Posts: 6,351
    edited 2006-03-29 15:24
    Thanks Jon, that was actually a question I asked myself after I posted "whats the effective size for the initial stack".



    ARgh, I just had to shoo away our new kitten from my work bench, she was trying to chew off one of the caps on my propeller board. Thankfully its not powered up.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    ·1+1=10
  • Kaos KiddKaos Kidd Posts: 614
    edited 2006-03-29 17:16
    So, the programmer would have to make sure the recursive routine wouldn't go deeper then what space permitted.
    So, for example, doing a mandlebrot set, the depth of each calculation would have to be limited...
    How would you know how deep you can go, other then trial and error?

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Just tossing my two bits worth into the bit bucket


    KK
    ·
  • Paul BakerPaul Baker Posts: 6,351
    edited 2006-03-29 18:05
    http://forums.parallax.com/showthread.php?p=577317

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    ·1+1=10
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2006-03-29 18:31
    Paul just posted a link to my stack monitor. It will monitor a stack up to 255 LONGs deep, which may be insufficient when recursion is involved. But you can always shift the result in the last statement by less than sixteen to get a scaled display.

    -Phil
  • Jon WilliamsJon Williams Posts: 6,491
    edited 2006-03-29 18:39
    Guys, I'm not a particularly clever programmer so I'm not suggesting that recursion will aways work -- it does in that case (Cog 0, with repeat limits used) and I was simply sharing that. I happened across that routine while looking up C style guidelines and gave it a try; I was happily surprised that it worked, and now have a better understanding that it may not in all cases, even with about 7000 longs available as a stack.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Jon Williams
    Applications Engineer, Parallax
  • Paul Sr.Paul Sr. Posts: 435
    edited 2006-03-29 18:46
    Paul Baker said...

    ARgh, I just had to shoo away our new kitten from my work bench, she was trying to chew off one of the caps on my propeller board. Thankfully its not powered up.

    Perhaps you should leave it powered......
  • Kaos KiddKaos Kidd Posts: 614
    edited 2006-03-31 19:07
    LOL @ pwssr... One zap and the cat will NOT do it again... garantieed!
    Anyway... I was toying with the idea of a real time 3D mandlebort generator / explorer.
    Recursion is the best method of generating a mandlebrot, with limits as well, but other methods do exist.
    The biggest unknown is the math. I know it's a matter of interpertation of data, and how you would like to see it applied.
    It's always fanicated me, the mandle sets that is, to the point where I use the program POV to create a 3D set of stills as the computations "slid" down a hill.
    I think it would be real neat to draw "dots" on the screen in real time computations, "sliding down, twisting" as the calculations proceede.
    The math is extensive, and would (might?) most likey require a math coprocessor (like the one Parallax has) for the floating point calculations.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Just tossing my two bits worth into the bit bucket


    KK
    ·
  • Paul BakerPaul Baker Posts: 6,351
    edited 2006-03-31 19:17
    Theres an object to do floating point calculations already availible, it would be faster than interfacing with an external serial coprocessor. It would still take quite a while to generate a single set.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    6+6=10 (Long live the duodecimal system!)
  • Jon WilliamsJon Williams Posts: 6,491
    edited 2006-03-31 19:52
    To Paul's point, Chip wrote an FP library in Spin that does a few of the essentials -- also shows the internals of FP. That said, in Spin it's not as fast as it could be and the library is not particularly feature rich. Our goal is to have an FP library written in Propeller assembly that will have many features and be very fast; ultimately it would be like adding a math coprocessor, but without having to use an external device.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Jon Williams
    Applications Engineer, Parallax
  • Kaos KiddKaos Kidd Posts: 614
    edited 2006-03-31 20:45
    Thats good.
    TO coin another's phrase, the more I learn, the less I can wait!

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Just tossing my two bits worth into the bit bucket


    KK
    ·
Sign In or Register to comment.