recursion

A

amanayin

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)
 
S

Sheldon Simms

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

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);
Click to expand...
^^^^^^^^^^
first call, first execution
17;
18; printf("The power of %d is %d\n",a,powered(b));
Click to expand...
^^^^^^^^^^
second call, second execution
 
A

August Derleth

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;
Click to expand...

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);
Click to expand...

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)
Click to expand...

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);
Click to expand...

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);

}
Click to expand...

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
Click to expand...

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

Michael Str.

August Derleth said:
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.


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.


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


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


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'?


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.
Click to expand...

Besides, preferably, if recursive function will be reentrant.

Michael
 
D

Daniel Vallstrom

August Derleth said:
on Sun 16 Nov 2003 11:05:39a:
[snip]
int powered(int x)
{
if(x < 1)
return 1;
else
return a * powered(x -1);

}
Click to expand...

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.
Click to expand...

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


Daniel Vallstrom
 
D

Daniel Vallstrom

amanayin said:
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);

}
Click to expand...

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
Click to expand...

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


Daniel Vallstrom
 
A

August Derleth

August Derleth said:
on Sun 16 Nov 2003 11:05:39a:
[snip]
int powered(int x)
{
if(x < 1)
return 1;
else
return a * powered(x -1);

}
Click to expand...

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.
Click to expand...

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


Daniel Vallstrom
Click to expand...

Ah! I see it now! Thank you.

(I still dislike the idea of a being a global, but at least the logic is correct.)
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Compiler problem....unique to C or compiler??? 17
strtok segfaults in CLI but not in GDB 21
overwriting memory 42
Memory corruption on freeing a pointer to pointer 172
gdb python how to output integer for examine memory 6
C/Ubuntu ][ Problem in Buffer Overflow logic 6
Where is my mistake? Why is s equal to minus infinity at some loop iterations? 0
problem of a program. 0

Members online

No members online now.
Total: 29 (members: 0, guests: 29)
Robots: 217

Forum statistics

Threads
473,764
Messages
2,569,565
Members
45,041
Latest member
RomeoFarnh

Latest Threads

Top