Velocity Reviews > recursion

# recursion

amanayin
Guest
Posts: n/a

 11-16-2003
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.
(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)

Sheldon Simms
Guest
Posts: n/a

 11-16-2003
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; }

August Derleth
Guest
Posts: n/a

 11-16-2003
amanayin <(E-Mail Removed)> wrote in
news:bp8e9i\$eg3\$(E-Mail Removed) 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

> 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.

Michael Str.
Guest
Posts: n/a

 11-17-2003
> amanayin <(E-Mail Removed)> wrote in
> news:bp8e9i\$eg3\$(E-Mail Removed) 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
>
> > 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

Daniel Vallstrom
Guest
Posts: n/a

 11-17-2003
> amanayin <(E-Mail Removed)> wrote in
> news:bp8e9i\$eg3\$(E-Mail Removed) 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
Guest
Posts: n/a

 11-17-2003
amanayin <(E-Mail Removed)> wrote in message news:<bp8e9i\$eg3\$(E-Mail Removed)>...
> 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

>
> __________________________________________________ ______
> __________________________________________________ ______
>
> 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

August Derleth
Guest
Posts: n/a

 11-17-2003
http://www.velocityreviews.com/forums/(E-Mail Removed) (Daniel Vallstrom) wrote in message news:<(E-Mail Removed). com>...
> > amanayin <(E-Mail Removed)> wrote in
> > news:bp8e9i\$eg3\$(E-Mail Removed) 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.)

amanayin
Guest
Posts: n/a

 11-18-2003

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM Kevin Porter MCSE 1 03-18-2006 05:56 AM Kevin Porter Microsoft Certification 0 03-16-2006 11:10 PM B McInnes Perl 4 11-04-2003 06:08 AM Tim Mohler Perl 1 09-16-2003 12:35 AM