please discuss recursive calls, program provided.

Discussion in 'C Programming' started by gdotone, Sep 8, 2013.

  1. OK:

    typedef unsigned long long number;

    static number fib_aux(number a, number b, int n)
    {
    if (n <= 1) return a;
    else return fib_aux(b, a+b, n-1);
    }

    number rfib(int n) { return fib_aux(1, 1, n); }

    number ifib(int n)
    {
    number a = 1, b = 1;
    while (n-- > 1) {
    number t = a;
    a = b;
    b = t + b;
    }
    return a;
    }

    Compiled separately (to prevent in-lining) from a driver:

    #include <stdio.h>
    #include <stdlib.h>

    typedef unsigned long long number;

    number rfib(int);
    number ifib(int);

    int main(int argc, char **argv)
    {
    int n = argc > 1 ? atoi(argv[1]) : 10;
    number sdiff = 0;
    for (int i = 1; i <= n; i++)
    sdiff += rfib(i) - ifib(i);
    printf("%lld\n", sdiff);
    return 0;
    }

    Here is the gprof output from running this program with argv[1] 100000
    (even with unsigned long long, you are not actually getting the right
    numbers, but it's hard to test otherwise).

    Flat profile:

    Each sample counts as 0.01 seconds.
    % cumulative self self total
    time seconds seconds calls us/call us/call name
    52.69 3.40 3.40 100000 34.04 34.04 ifib
    48.32 6.53 3.12 100000 31.21 31.21 rfib

    I will admit to picking the best of three to make a point, but in all
    cases ifib and rfib were timed at essentially the same speed -- which
    comes out faster is in statistical noise. (Compiled with -O2, though it
    may depend on compiler version.)
    I think the recursive function makes the rule that defines the sequence
    much clearer than the loop does, but I accept that that may be a matter
    of opinion. That aside, I don't think you can say that it's not
    "remotely near as clear" as the alternatives.
     
    Ben Bacarisse, Sep 10, 2013
    #21
    1. Advertisements

  2. .... and my favourite Haskell Fibonacci sequence

    fib = 1 : 1 : map zipWith (+) fib (tail fib)

    which is, I think, due to David Turner. You get an unbounded list to do
    with as you please.

    <snip>
     
    Ben Bacarisse, Sep 10, 2013
    #22
    1. Advertisements

  3. gdotone

    Öö Tiib Guest

    For example painting a complex region that should be same-colored.
    Humans do it quite similarly to flood fill algorithm. It is hard to
    imagine non-recursive and efficient flood fill algorithm. For other
    example searching something from building methodically by opening
    rooms, cabinets in rooms, drawers in cabinets, boxes in drawers and
    closing the opened in reverse order.
    Things like that Ackermann function make recursion to sound like a tool
    for rather unusual problems.
     
    Öö Tiib, Sep 10, 2013
    #23
  4. gdotone

    Phil Carmody Guest

    Looking at the code, the first thing that went through my mind was
    "they should compile to essentially the same thing".

    I don't know what they do on your platform, but GCC on POWER supports
    that rather well:

    00000000 <rfib>:
    typedef unsigned long long number;

    static number fib_aux(number a, number b, int n)
    {
    if (n <= 1) return a;
    0: 2f 83 00 01 cmpwi cr7,r3,1
    4: 39 20 00 00 li r9,0
    8: 39 40 00 01 li r10,1
    c: 40 9d 00 40 ble- cr7,4c <rfib+0x4c>
    10: 38 63 ff ff addi r3,r3,-1
    14: 39 60 00 00 li r11,0
    18: 7c 69 03 a6 mtctr r3
    1c: 39 80 00 01 li r12,1
    20: 48 00 00 20 b 40 <rfib+0x40>
    24: 60 00 00 00 nop
    28: 60 00 00 00 nop
    2c: 60 00 00 00 nop
    30: 7d 4c 53 78 mr r12,r10
    34: 7d 2b 4b 78 mr r11,r9
    38: 7d 0a 43 78 mr r10,r8
    3c: 7c e9 3b 78 mr r9,r7
    else return fib_aux(b, a+b, n-1);
    40: 7d 0a 60 14 addc r8,r10,r12
    44: 7c e9 59 14 adde r7,r9,r11
    typedef unsigned long long number;

    static number fib_aux(number a, number b, int n)
    {
    if (n <= 1) return a;
    48: 42 00 ff e8 bdnz+ 30 <rfib+0x30>
    else return fib_aux(b, a+b, n-1);
    }

    number rfib(int n) { return fib_aux(1, 1, n); }
    4c: 7d 44 53 78 mr r4,r10
    50: 7d 23 4b 78 mr r3,r9
    54: 4e 80 00 20 blr
    58: 60 00 00 00 nop
    5c: 60 00 00 00 nop

    00000060 <ifib>:

    number ifib(int n)
    {
    number a = 1, b = 1;
    while (n-- > 1) {
    60: 2f 83 00 01 cmpwi cr7,r3,1
    64: 39 20 00 00 li r9,0
    68: 39 40 00 01 li r10,1
    6c: 40 9d 00 40 ble- cr7,ac <ifib+0x4c>
    70: 38 63 ff ff addi r3,r3,-1
    74: 39 60 00 00 li r11,0
    78: 7c 69 03 a6 mtctr r3
    7c: 39 80 00 01 li r12,1
    80: 48 00 00 18 b 98 <ifib+0x38>
    84: 60 00 00 00 nop
    88: 60 00 00 00 nop
    8c: 60 00 00 00 nop
    90: 7d 0a 43 78 mr r10,r8
    94: 7c e9 3b 78 mr r9,r7
    number t = a;
    a = b;
    b = t + b;
    98: 7d 0a 60 14 addc r8,r10,r12
    9c: 7c e9 59 14 adde r7,r9,r11
    number rfib(int n) { return fib_aux(1, 1, n); }

    number ifib(int n)
    {
    number a = 1, b = 1;
    while (n-- > 1) {
    a0: 7d 4c 53 78 mr r12,r10
    a4: 7d 2b 4b 78 mr r11,r9
    a8: 42 00 ff e8 bdnz+ 90 <ifib+0x30>
    number t = a;
    a = b;
    b = t + b;
    }
    return a;
    }
    ac: 7d 44 53 78 mr r4,r10
    b0: 7d 23 4b 78 mr r3,r9
    b4: 4e 80 00 20 blr


    A POWER machine (running debian stable) is far more metronomic
    than many other machines, and the lack of statistical noise is
    quite interesting:

    % cumulative self self total
    time seconds seconds calls us/call us/call name
    50.24 12.60 12.60 100000 126.00 126.00 ifib
    49.76 25.08 12.48 100000 124.80 124.80 rfib

    50.28 12.61 12.61 100000 126.10 126.10 ifib
    49.72 25.08 12.47 100000 124.70 124.70 rfib

    50.22 12.60 12.60 100000 126.00 126.00 rfib
    49.78 25.09 12.49 100000 124.90 124.90 ifib
    Your recursive function would be my method of choice, thanks for going
    to the effort of selling tail recursion so effectively.

    Phil
     
    Phil Carmody, Sep 10, 2013
    #24
  5. gdotone

    Joe Pfeiffer Guest

    Ummm... you're right, this is certainly in the same ballpark of
    efficiency. As for clarity, that must necessarily be a matter of
    opinion -- but this doesn't strike me clear at all without a lot of
    effort devoted to reading it.
     
    Joe Pfeiffer, Sep 10, 2013
    #25
  6. [/QUOTE]
    Yes, they are, essentially, the same algorithm. The only slight
    difference is that the shuffling of 'a' though a temporary can be
    avoided using parameter passing semantics.
    For the record, here's what gcc 4.7.3 makes of it on my laptop. I've
    snipped the junk and put the two side-by-side:

    rfib: ifib:
    ..LFB1: .LFB2:
    cmpl $1, %edi cmpl $1, %edi
    movl $1, %eax leal -1(%rdi), %edx
    jle .L4 movl $1, %eax
    movl $1, %edx jle .L10
    jmp .L3 movl $1, %ecx
    ..L5: jmp .L9
    movq %rcx, %rax .L11:
    ..L3: movq %rsi, %rax
    subl $1, %edi .L9:
    leaq (%rdx,%rax), %rcx subl $1, %edx
    movq %rax, %rdx leaq (%rcx,%rax), %rsi
    cmpl $1, %edi movq %rax, %rcx
    jne .L5 jne .L11
    rep rep
    ret ret
    ..L4: .L10:
    rep rep
    ret ret

    <snip>
     
    Ben Bacarisse, Sep 10, 2013
    #26
  7. gdotone

    Phil Carmody Guest

    I'm perfectly prepared to believe I'm in a minority, but few things
    are more natural than recursion to me.
    A journey of a thousand miles begins with a single step, and continues
    with a slightly less long journey that can be similarly addressed.

    Phil
     
    Phil Carmody, Sep 10, 2013
    #27
  8. Ummm... you're right, this is certainly in the same ballpark of
    efficiency.[/QUOTE]

    Ballpark?! They're in the same back yard! You really can't separate
    them, at least on the couple of architectures that has been posted.
    I find that odd. rfib_aux is two lines (it would be one with a
    conditional expression) and needs a one-line call to set up the initial
    values. ifib has the same one-line initialisation, but needs five lines
    and has an extra variable whose role is unrelated to the overall purpose
    of the loop. My point, though, is not to try to bludgeon you into
    saying it's clear, but simply that, since the code so short, any lack of
    clarity probably stems from a difference in the way we think about code.
    In other words, I don't think you can argue that any lack of clarity is
    intrinsic to the code.
     
    Ben Bacarisse, Sep 10, 2013
    #28
  9. gdotone

    Eric Sosman Guest

    In a journey of a thousand miles there's a 95% chance that
    you'll miss connections at O'Hare.
     
    Eric Sosman, Sep 10, 2013
    #29
  10. gdotone

    James Kuyper Guest

    If my flight goes through Atlanta rather than O'Hare (which is usually
    the case), I suppose you could argue that it counts as missing the
    connection at O'Hare, but that doesn't seem quite right.

    [comp.lang.c content dropping rapidly]
     
    James Kuyper, Sep 10, 2013
    #30
  11. Hello,

    It is always optimized to use Recursive Functions whenever you have large data to process, Since Recursive function works on stack.
    To optimize the processing, you can also use the likely and not likely for if and else block to improve the performance.

    Find below link useful to understand the Recursive best explained.
    http://programmers.stackexchange.com/questions/25052/in-plain-english-what-is-recursion

    Thanks,
    Nitin Tripathi
     
    Nitin Tripathi, Sep 10, 2013
    #31
  12. gdotone

    James Kuyper Guest

    On 09/10/2013 03:47 PM, Nitin Tripathi wrote:
    ....
    Statements involving absolute terms like "always" should generally be
    treated with suspicion: "always" is usually an exaggeration, at best,
    and is often outright wrong. This is a prime example.

    Let's leave aside the ever-controversial question of whether a stack is
    even required for a conforming C implementation.

    Are you suggesting that non-recursive functions don't work on the stack?
    Most of the functions I've ever written are non-recursive, and most of
    them made heavy use of the stack. The few recursive functions I've
    written have usually involved dynamically allocated N-ary tree
    structures, so the recursion mainly involve the heap, not the stack.

    It seems to me that both the structure of the data and the nature of the
    processing to be performed are much more important than the size of the
    data, in determining whether recursion is a good idea.
     
    James Kuyper, Sep 10, 2013
    #32
  13. Naive floodfill is

    if(pixel == target)
    {
    pixel = value;
    floodfill(NORTH)
    floodfill(SOUTH);
    floodfill(EAST);
    floodfill(WEST);
    }

    that's OK for small images. But on a medium-sized to large image
    you'll find it's very slow, and can blow the stack. The problem is
    that it doesn't have good characteristics for maintaining a
    neat tidal edge, you've got too many calls to filled regions.

    A scaleable floodfill fills in a horizontal line, then keeps a queue of pixels above and pixels below.
     
    Malcolm McLean, Sep 11, 2013
    #33
  14. gdotone

    Öö Tiib Guest

    :D It is easy to produce inefficient algorithms for anything.
    Recursive algorithm does same without queues.
     
    Öö Tiib, Sep 11, 2013
    #34
  15. gdotone

    Phil Carmody Guest

    Curiously, I'd have said that if any sweeping generalisation
    along those lines were to be made it would have been the
    exact opposite way round! I'd much rather operate repeatedly
    in a huge object (iteration) than pass it around as a parameter
    (recursion).

    Phil
     
    Phil Carmody, Sep 11, 2013
    #35
  16. gdotone

    JohnF Guest

    A little off-topic (I'm interested in the floodfill, not so
    much recursion, per se), but would the scaleable floodfill
    work for something like...
    .. .
    |\ /|
    | \ / |
    | \ / |
    | \ / ? |
    | x \ /left|
    | \/blank|
    | |
    | |
    +------------+
    If you start at point x (any point in the upper left-hand-side
    triangle), won't the entire region of the upper right-hand-side
    triangle be missed? Thanks,
     
    JohnF, Sep 12, 2013
    #36
  17. gdotone

    Ike Naar Guest

    Not necessarily.
    The straightforward (naive?) recursive solution is horribly
    inefficient, but very efficient recursive solutions do exist.
     
    Ike Naar, Sep 12, 2013
    #37
  18. But as an example for beginning programmers, you have to expect
    the most straightforward.

    The usual solution that I have seen in the past is to keep a cache
    of previously computed values. Since Fibonacci increases exponentially,
    the cache won't be very big, and so can have a static size.
    Also, it isn't very obvious to beginners.

    -- glen
     
    glen herrmannsfeldt, Sep 12, 2013
    #38
  19. gdotone

    Ike Naar Guest

    Very nice, a recursive solution that computes Fib(n) in linear time.

    Here's one that should be more efficient for large n,
    it computes Fib(n) in logarithmic time:

    typedef unsigned long long num;

    static num fib_aux(int n, num p, num q, num r, num x, num y)
    {
    if (n == 0)
    {
    return x;
    }
    else if (n % 2 == 0)
    {
    return fib_aux(n/2, p*p+q*q, (p+r)*q, q*q+r*r, x, y);
    }
    else
    {
    return fib_aux(n-1, p, q, r, p*x+q*y, q*x+r*y);
    }
    }

    num fib(int n)
    {
    return fib_aux(n, 0, 1, 1, 0, 1);
    }

    It's based on the observation that (in matrix notation)

    [ Fib(n) ] [ p q ] [ 0 ]
    [ Fib(n+1) ] = [ q r ] * [ 1 ]

    where
    n
    [ p q ] [ 0 1 ]
    [ q r ] = [ 1 1 ]

    Of course the recursive algorithm can be easily transformed
    to an iterative version.
     
    Ike Naar, Sep 12, 2013
    #39
  20. No, because you patch it to check for stray NORTH pixels
    when you extend the scan line.
    You can devise complex shapes where the queues become very big. But normally you just need 2 * width queues, so
    there's limited memory reallocation.
     
    Malcolm McLean, Sep 12, 2013
    #40
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.