recursion

Discussion in 'C Programming' started by amanayin, Nov 16, 2003.

  1. amanayin

    amanayin Guest

    trying to understand recursion
    question why does this program run twice before
    output is displayed

    1; /* ex4-11.c program to find the power of a number */
    2;
    3; #include<stdio.h>
    4;
    5; int a,b,y;
    6;
    7; int powered(int x);
    8;
    9; int main(void)
    10; {
    11; printf("Enter a number: ");
    12; scanf("%d",&a);
    13; printf("Enter the number to find power: ");
    14; scanf("%d",&b);
    15;
    16; powered(b);
    17;
    18; printf("The power of %d is %d\n",a,powered(b));
    19; return 0;
    20; }

    int powered(int x)
    {
    if(x < 1)
    return 1;
    else
    return a * powered(x -1);

    }

    ________________________________________________________
    ________________________________________________________

    Then if i change line 16 from (powered(b); to y = powered(b);
    and the end of the printf statement as well it only runs
    once before output is displayed

    ______________________________________________________
    Out put for first example
    ______________________________________________________
    GNU DDD 3.3.1 (i386-suse-linux), by Dorothea Lütkehaus and Andreas Zeller.
    Copyright © 1995-1999 Technische Universität Braunschweig, Germany.
    Copyright © 1999-2001 Universität Passau, Germany.
    (gdb) break main
    Breakpoint 1 at 0x8048384: file ex4-11.c, line 11.
    (gdb) run

    Breakpoint 1, main () at ex4-11.c:11
    (gdb) step
    (gdb) step
    Enter a number: 4
    (gdb) next
    (gdb) next
    Enter the number to find power: 5
    (gdb) step
    powered (x=5) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=4) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=3) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=2) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=1) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=0) at ex4-11.c:24
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    main () at ex4-11.c:18
    (gdb) step
    powered (x=5) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=4) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=3) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=2) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=1) at ex4-11.c:24
    (gdb) step
    (gdb) step
    powered (x=0) at ex4-11.c:24
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    (gdb) step
    The power of 4 is 1024
    main () at ex4-11.c:19
    /home/glen/lsamc/week1/d4/ex4/ex4-11.c:19:317:beg:0x804840c
    (gdb) step
    (gdb) step
    0x4003a8ae in __libc_start_main () from /lib/libc.so.6
    (gdb) step
    Single stepping until exit from function __libc_start_main,
    which has no line number information.

    Program exited normally.
    (gdb) step
    The program is not being run.
    (gdb)
     
    amanayin, Nov 16, 2003
    #1
    1. Advertising

  2. On Sun, 16 Nov 2003 18:05:39 +0000, amanayin wrote:

    > trying to understand recursion
    > question why does this program run twice before
    > output is displayed


    Your question has nothing to do with recursion. Your
    code calls the function powered() twice and so it
    executes twice. What is surprising about that?

    > 1; /* ex4-11.c program to find the power of a number */
    > 2;
    > 3; #include<stdio.h>
    > 4;
    > 5; int a,b,y;
    > 6;
    > 7; int powered(int x);
    > 8;
    > 9; int main(void)
    > 10; {
    > 11; printf("Enter a number: ");
    > 12; scanf("%d",&a);
    > 13; printf("Enter the number to find power: ");
    > 14; scanf("%d",&b);
    > 15;
    > 16; powered(b);

    ^^^^^^^^^^
    first call, first execution

    > 17;
    > 18; printf("The power of %d is %d\n",a,powered(b));

    ^^^^^^^^^^
    second call, second execution

    > 19; return 0;
    > 20; }
     
    Sheldon Simms, Nov 16, 2003
    #2
    1. Advertising

  3. amanayin <> wrote in
    news:bp8e9i$eg3$ on Sun 16 Nov 2003 11:05:39a:

    > trying to understand recursion
    > question why does this program run twice before
    > output is displayed
    >
    > 1; /* ex4-11.c program to find the power of a number */
    > 2;
    > 3; #include<stdio.h>
    > 4;
    > 5; int a,b,y;


    Why are you using globals? It's usually better to simply pass in every
    argument the subroutine needs explicitly, and to keep most variables local
    to a subroutine.

    Secondly, where is the variable y used? I can't see it anywhere else in
    your code.

    > 6;
    > 7; int powered(int x);


    As per my above comment, consider writing this like this:

    /* Raise x to the y'th power. */
    int powered(int x, int y);

    That way, you don't need to depend upon a global variable to be set to any
    value: You can simply pass in the two values and be certain it will work.

    On second thought, if you meant to write a factorial subroutine, you only
    need the one variable, but you should probably change the name.

    > 8;
    > 9; int main(void)


    This, however, is correct. You'd be amazed at how often people get this
    line wrong.

    > 10; {
    > 11; printf("Enter a number: ");
    > 12; scanf("%d",&a);
    > 13; printf("Enter the number to find power: ");
    > 14; scanf("%d",&b);
    > 15;
    > 16; powered(b);


    You're throwing away the return value of this call. You've basically
    called it uselessly.

    > 17;
    > 18; printf("The power of %d is %d\n",a,powered(b));
    > 19; return 0;
    > 20; }
    >
    > int powered(int x)
    > {
    > if(x < 1)
    > return 1;
    > else
    > return a * powered(x -1);
    >
    >}


    Maybe I'm the one with the problem, but I don't quite get the point of
    this subroutine: It will not raise a to the x'th power. It will simply
    multiply a by all of the numbers from x-1 to 1 in turn.

    The only other thing I could think of is that you meant to write a
    factorial subroutine, in which case you can replace a with x and be in
    business. That is, in fact, the classic way to write a factorial
    subroutine. But if that's what you meant, why did you call it `powered'?

    >
    > ________________________________________________________
    > ________________________________________________________
    >
    > Then if i change line 16 from (powered(b); to y = powered(b);
    > and the end of the printf statement as well it only runs
    > once before output is displayed


    If you change the end of the printf statement to just y, you've stored the
    return value from powered and are simply printing it out now. powered only
    needs to run once in this instance.

    In the example you posted, however, powered must run twice, because the
    first time you're throwing away its value.
     
    August Derleth, Nov 16, 2003
    #3
  4. amanayin

    Michael Str. Guest

    August Derleth <libertarian232003**@onewest.net> wrote in message news:<Xns94358F88ED49libertarianonewestne@63.223.8.240>...
    > amanayin <> wrote in
    > news:bp8e9i$eg3$ on Sun 16 Nov 2003 11:05:39a:
    >
    > > trying to understand recursion
    > > question why does this program run twice before
    > > output is displayed
    > >
    > > 1; /* ex4-11.c program to find the power of a number */
    > > 2;
    > > 3; #include<stdio.h>
    > > 4;
    > > 5; int a,b,y;

    >
    > Why are you using globals? It's usually better to simply pass in every
    > argument the subroutine needs explicitly, and to keep most variables local
    > to a subroutine.
    >
    > Secondly, where is the variable y used? I can't see it anywhere else in
    > your code.
    >
    > > 6;
    > > 7; int powered(int x);

    >
    > As per my above comment, consider writing this like this:
    >
    > /* Raise x to the y'th power. */
    > int powered(int x, int y);
    >
    > That way, you don't need to depend upon a global variable to be set to any
    > value: You can simply pass in the two values and be certain it will work.
    >
    > On second thought, if you meant to write a factorial subroutine, you only
    > need the one variable, but you should probably change the name.
    >
    > > 8;
    > > 9; int main(void)

    >
    > This, however, is correct. You'd be amazed at how often people get this
    > line wrong.
    >
    > > 10; {
    > > 11; printf("Enter a number: ");
    > > 12; scanf("%d",&a);
    > > 13; printf("Enter the number to find power: ");
    > > 14; scanf("%d",&b);
    > > 15;
    > > 16; powered(b);

    >
    > You're throwing away the return value of this call. You've basically
    > called it uselessly.
    >
    > > 17;
    > > 18; printf("The power of %d is %d\n",a,powered(b));
    > > 19; return 0;
    > > 20; }
    > >
    > > int powered(int x)
    > > {
    > > if(x < 1)
    > > return 1;
    > > else
    > > return a * powered(x -1);
    > >
    > >}

    >
    > Maybe I'm the one with the problem, but I don't quite get the point of
    > this subroutine: It will not raise a to the x'th power. It will simply
    > multiply a by all of the numbers from x-1 to 1 in turn.
    >
    > The only other thing I could think of is that you meant to write a
    > factorial subroutine, in which case you can replace a with x and be in
    > business. That is, in fact, the classic way to write a factorial
    > subroutine. But if that's what you meant, why did you call it `powered'?
    >
    > >
    > > ________________________________________________________
    > > ________________________________________________________
    > >
    > > Then if i change line 16 from (powered(b); to y = powered(b);
    > > and the end of the printf statement as well it only runs
    > > once before output is displayed

    >
    > If you change the end of the printf statement to just y, you've stored the
    > return value from powered and are simply printing it out now. powered only
    > needs to run once in this instance.
    >
    > In the example you posted, however, powered must run twice, because the
    > first time you're throwing away its value.


    Besides, preferably, if recursive function will be reentrant.

    Michael
     
    Michael Str., Nov 17, 2003
    #4
  5. August Derleth <libertarian232003**@onewest.net> wrote in message news:<Xns94358F88ED49libertarianonewestne@63.223.8.240>...
    > amanayin <> wrote in
    > news:bp8e9i$eg3$ on Sun 16 Nov 2003 11:05:39a:


    [snip]

    > > int powered(int x)
    > > {
    > > if(x < 1)
    > > return 1;
    > > else
    > > return a * powered(x -1);
    > >
    > >}

    >
    > Maybe I'm the one with the problem, but I don't quite get the point of
    > this subroutine: It will not raise a to the x'th power.


    Yes it will. Reason inductively: powered(0) == 1 == a^0; powered(n+1) ==
    a * powered(n) == a * a^n == a^(n+1).


    Daniel Vallstrom
     
    Daniel Vallstrom, Nov 17, 2003
    #5
  6. amanayin <> wrote in message news:<bp8e9i$eg3$>...
    > trying to understand recursion
    > question why does this program run twice before
    > output is displayed
    >
    > 1; /* ex4-11.c program to find the power of a number */
    > 2;
    > 3; #include<stdio.h>
    > 4;
    > 5; int a,b,y;
    > 6;
    > 7; int powered(int x);
    > 8;
    > 9; int main(void)
    > 10; {
    > 11; printf("Enter a number: ");
    > 12; scanf("%d",&a);
    > 13; printf("Enter the number to find power: ");
    > 14; scanf("%d",&b);
    > 15;
    > 16; powered(b);
    > 17;
    > 18; printf("The power of %d is %d\n",a,powered(b));
    > 19; return 0;
    > 20; }
    >
    > int powered(int x)
    > {
    > if(x < 1)
    > return 1;
    > else
    > return a * powered(x -1);
    >
    > }


    If you by "this program" mean the powered function, the reason why
    it's called twice is of course because you call it twice, on row 16
    and 18. Perhaps you just missed that.

    Otherwise the answer is that in theory it would be possible
    for the compiler/interpreter to notice that the second
    powered(b) call has already been made on row 16 so it could just
    save the result from then and use that saved result directly without
    computing it twice. In practice though it won't work that way generally
    as you noticed because it's too hard a problem for compilers to solve
    with too little benefit. (I'm no compiler expert though. Perhaps some
    compilers really do try this optimization? Especially ones for
    functional languages since there won't be side effects there?)
    If you don't want any recomputations, the standard straightforward
    technique is memoization where you save the result of a computation
    in some table. Then, before you carry out a computation, you check the
    table and see if the computation has already been made.


    >
    > ________________________________________________________
    > ________________________________________________________
    >
    > Then if i change line 16 from (powered(b); to y = powered(b);
    > and the end of the printf statement as well it only runs
    > once before output is displayed


    This could be called some sort of vanilla memoization I guess.


    Daniel Vallstrom
     
    Daniel Vallstrom, Nov 17, 2003
    #6
  7. (Daniel Vallstrom) wrote in message news:<>...
    > August Derleth <libertarian232003**@onewest.net> wrote in message news:<Xns94358F88ED49libertarianonewestne@63.223.8.240>...
    > > amanayin <> wrote in
    > > news:bp8e9i$eg3$ on Sun 16 Nov 2003 11:05:39a:

    >
    > [snip]
    >
    > > > int powered(int x)
    > > > {
    > > > if(x < 1)
    > > > return 1;
    > > > else
    > > > return a * powered(x -1);
    > > >
    > > >}

    > >
    > > Maybe I'm the one with the problem, but I don't quite get the point of
    > > this subroutine: It will not raise a to the x'th power.

    >
    > Yes it will. Reason inductively: powered(0) == 1 == a^0; powered(n+1) ==
    > a * powered(n) == a * a^n == a^(n+1).
    >
    >
    > Daniel Vallstrom


    Ah! I see it now! Thank you.

    (I still dislike the idea of a being a global, but at least the logic is correct.)
     
    August Derleth, Nov 17, 2003
    #7
  8. amanayin

    amanayin Guest

    Thanks for all your help
     
    amanayin, Nov 18, 2003
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim Mohler
    Replies:
    1
    Views:
    445
    Steve Grazzini
    Sep 16, 2003
  2. B McInnes

    recursion with perl

    B McInnes, Nov 1, 2003, in forum: Perl
    Replies:
    4
    Views:
    4,131
    B McInnes
    Nov 4, 2003
  3. Chris

    Recursion Query

    Chris, May 17, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    442
    avnrao
    May 17, 2004
  4. Iain
    Replies:
    3
    Views:
    1,815
    Robbe Morris [C# MVP]
    Mar 9, 2006
  5. Replies:
    8
    Views:
    744
    John Reye
    Apr 26, 2012
Loading...

Share This Page