# recursion

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

1. ### amanayinGuest

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)

amanayin, Nov 16, 2003

2. ### Sheldon SimmsGuest

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

3. ### August DerlethGuest

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

> 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
4. ### Michael Str.Guest

> 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
>
> > 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
5. ### Daniel VallstromGuest

> 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
6. ### Daniel VallstromGuest

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

>
> ________________________________________________________
> ________________________________________________________
>
> 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
7. ### August DerlethGuest

(Daniel Vallstrom) wrote in message news:<>...
> > 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
8. ### amanayinGuest

amanayin, Nov 18, 2003