Results 1 to 7 of 7

Thread: Various types of recursion

Share/Bookmark
  1. #1
    Super Moderator Petr Schreiber's Avatar
    Join Date
    Aug 2005
    Location
    Brno - Czech Republic
    Posts
    6,776
    Blog Entries
    3
    Rep Power
    690

    Various types of recursion

    Learning for exam,

    I had to create example on different kinds of recursion to really see they behave as described.
    Could serve as some kind of test whether recursion works ok:
    ' -- Various types of recursion
    
    Uses "Console"
    
    PrintL "Ackermann function"
    PrintL ack(3, 4)
    PrintL
    
    PrintL "Fibonacci"
    PrintL fib(5)
    PrintL
    
    PrintL "Factorial"
    PrintL fact(5)
    PrintL
    
    PrintL "Greatest common divisor"
    PrintL gcd(513, 27)
    PrintL
    
    WaitKey
    
    ' -- Nested recursion: Recursive call to function contains recursive call to itself in the arguments
    ' -- Ackermann function
    Function ack(x As Number, y As Number) As Number
     If x = 0 Then Return y+1
     If y = 0 Then Return ack(x-1, 1) 
     Return ack(x-1, ack(x, y-1))
    End Function
    
    ' -- Cascade (tree) recursion: Multiple occuriences of recursive call appear in one expression, but without any nesting
    ' -- Fibonacci
    Function fib(n As Number) As Number
     If n <= 1 Then Return 1 
     Return fib(n-2)+fib(n-1)
    End Function
    
    ' -- Linear recursion: Each alternative of definition contains 1 recursive call at max.
    ' -- Factorial
    Function fact(n As Number) As Number
     If n = 0 Then Return 1 
     Return n * fact(n-1)
    End Function
    
    ' -- End recursion: Special case of linear recursion, where recursive call is the last operation of specific alternative of definition
    ' -- Greatest common divisor
    Function gcd(x As Number, y As Number) As Number
     If x = y Then Return x
     If x > y Then Return gcd(x-y, y)
     Return gcd(x, y-x)
    End Function
    
    You can take a walk through the code using debugger, to watch it call itself.


    Petr
    Last edited by ErosOlmi; 21-01-2011 at 00:37.
    Learn 3D graphics with ThinBASIC, learn TBGL!
    Windows 7 64bit - Intel Core 2 Duo T6600 @ 2.2GHz - 4 GB RAM - NVIDIA GeForce G210M 512MB
    Windows 8 64bit - Intel Core i5-3350P @ 3.1GHz - 8 GB RAM - NVIDIA GeForce GT640 3GB

  2. #2
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Blog Entries
    29
    Rep Power
    145

    Re: Various types of recursion

    [font=courier new]How about, composition of recursive functions?


    Dan :P

    Uses "console"
    
    'This script runs OK.
    'But, it is easy to cause "stack" overflow in the function gcd().
    'For me, gcd(2585, 1), results in Windows saying the program has stopped working.
    
    Function TBMain()
    Console_WriteLine(gcd(fib(fact(ack(1, 1))), 13))
    Console_WriteLine
    Console_WriteLine("Done. Press a key.")
    WaitKey
    End Function
    
     
    ' -- Nested recursion: Recursive call to function contains recursive call to itself in the arguments
    ' -- Ackermann function
    Function ack(x As Number, y As Number) As Number
     If x = 0 Then Return y+1
     If y = 0 Then Return ack(x-1, 1) 
     Return ack(x-1, ack(x, y-1))
    End Function
     
    ' -- Cascade (tree) recursion: Multiple occurrences of recursive call appear in one expression, but without any nesting
    ' -- Fibonacci
    Function fib(n As Number) As Number
     If n <= 1 Then Return 1 
     Return fib(n-2)+fib(n-1)
    End Function
     
    ' -- Linear recursion: Each alternative of definition contains 1 recursive call at max.
    ' -- Factorial
    Function fact(n As Number) As Number
     If n = 0 Then Return 1 
     Return n * fact(n-1)
    End Function
     
    ' -- End recursion: Special case of linear recursion, where recursive call is the last operation of specific alternative of definition
    ' -- Greatest common divisor
    Function gcd(x As Number, y As Number) As Number
     If x = y Then Return x
     If x > y Then Return gcd(x-y, y)
     Return gcd(x, y-x)
    End Function
    
    Last edited by ErosOlmi; 21-01-2011 at 00:38.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  3. #3
    Super Moderator Petr Schreiber's Avatar
    Join Date
    Aug 2005
    Location
    Brno - Czech Republic
    Posts
    6,776
    Blog Entries
    3
    Rep Power
    690

    Re: Various types of recursion

    That is recursion festival what you posted here

    I do not use recursion very much in my programs, as it is usually slower than other methods.
    I was learning for LISP exam, but as the debugger in LispWorks did not became my friend, I coded it in TB to see what it does.


    Petr
    Learn 3D graphics with ThinBASIC, learn TBGL!
    Windows 7 64bit - Intel Core 2 Duo T6600 @ 2.2GHz - 4 GB RAM - NVIDIA GeForce G210M 512MB
    Windows 8 64bit - Intel Core i5-3350P @ 3.1GHz - 8 GB RAM - NVIDIA GeForce GT640 3GB

  4. #4

    Re: Various types of recursion


    I found it is almost impossible to do without recursion in certain situations: when compiling BASIC statements expressions may occur in the arguments of function calls. These expressions may contain further functions ...

    The only practical way to resolve these nested structures which involve quite complicated parsing - is to use recursion. But it is not my first choice of strategy and it can be avoided most of the time, using iteration and array indexing instead.

    Charles

  5. #5
    Super Moderator Petr Schreiber's Avatar
    Join Date
    Aug 2005
    Location
    Brno - Czech Republic
    Posts
    6,776
    Blog Entries
    3
    Rep Power
    690

    Re: Various types of recursion

    You are right,

    in some cases you simply need to use recursion.
    I just wanted to say it is not the best solution in some situations, like the calculation of fibbonacci sequence.


    Petr
    Learn 3D graphics with ThinBASIC, learn TBGL!
    Windows 7 64bit - Intel Core 2 Duo T6600 @ 2.2GHz - 4 GB RAM - NVIDIA GeForce G210M 512MB
    Windows 8 64bit - Intel Core i5-3350P @ 3.1GHz - 8 GB RAM - NVIDIA GeForce GT640 3GB

  6. #6
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Blog Entries
    29
    Rep Power
    145

    Re: Various types of recursion

    [font=courier new]I looked, and you can define the Ackermann Function non-recursively, using Knuth's up-arrow
    notation.

    ^ (m-2)
    A(m,n) = 2 | (n+3) - 3

    Dan

    http://en.wikipedia.org/wiki/Ackermann_function

    http://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

    http://www.daviddarling.info/encyclo..._function.html
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  7. #7
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Blog Entries
    29
    Rep Power
    145

    Re: Various types of recursion

    [font=courier new]I posted this last year at Ionic Wind.
    But, since it demonstrates recursion, I'll post it here.


    Dan :P


    We're Proud to Announce to One and All
    (S.Howard, D.Baron)

    We're proud to announce,
    to one and all.
    We've been inducted into,
    the Poets' Hall.

    The committee chose the best poem,
    of all time.
    And we modestly acknowledge,
    they selected this rhyme.

    We received two blue ribbon awards,
    and two bronze statues too.
    That show Shakespeare astride,
    his famous pet kangaroo.

    They made a beautiful plaque,
    with our names engraved.
    And through the entire event,
    we were wonderfully behaved.

    The plaque will hang for eternity,
    in the Poets' Hall.
    Reading as follows,
    on the Honors' Wall.
    "The best poem ever either small or tall,
    'We're Proud to Announce to One and All'".

    They rolled out the red carpet,
    and had a parade.
    They presented us each with,
    ten pretty young maids.

    They announced on loudspeakers,
    "Hail the kings of the poem !".
    And when the parade finished,
    they graciously took us both hoem ...
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Similar Threads

  1. Types
    By kryton9 in forum TBGL General
    Replies: 8
    Last Post: 26-11-2006, 00:36

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •