can not perform recursion function correctly

 can not perform recursion function correctly

hi: I want to use recursion function to transform a integer from binary form to ascii form. But the result is wrong.I don't why ,please help to analyse.

soure code:

void
binary_to_ascii(unsigned int value)
{

   unsigned int quotient;
   quotient = value/10;
   if(quotient !=0 )
       binary_to_ascii(quotient);
   putchar(value%10+'0');

}


int
main()
{
 while(1){
    binary_to_ascii(4267);
  }
}

I want to produce characters '4','2','6','7' in sequence. but the result is '4','4','4'. I don't know what is wrong with my code.

 RE: can not perform recursion function correctly

Look up recursive or reentrant in the C51 user's manual. You will see that you must use the keyword reentrant so that a pseudo stack can be built to save any registers used in the reentrant function.
Bradford

 Don't do this in C51!!

For the same reasons that function pointers are best avoided in C51 - see your other thread: http://www.keil.com/forum/17469/

Any recursive algorithm can be restructured into an iterative one - or why not just use sprintf??!

 RE: Don't do this in C51!!

A recursive function requires a stack for storing the return values - check how large this stack must be for each iteration of a recursive function.

It is trivial to rewrite a very large group of recursive functions into iterative functions. In this case, the trivial implementation will produce the characters in reverse order - but each iteration only needs one byte to store one character until they are ready to be emitted in the correct order.

Recursion is a very useful concept. But it is best left for problems where the complexity of storing state information and making subdivision decisions gets very complex with a non-recursive method.

Any linear recursive algorithm can be trivially rewritten as an iteration. Many branching recursive algorithms (tree walking for example) can be trivially rewritten with an explicit state queue. It's quite seldom that a iterative solution can't be implemented in an obvious way.

 RE: A recursive function requires a stack for storing the return values

It also requires some way to pass parameters & maintain local variables so that each "recursion" doesn't corrupt the data & parameters of previous recursions; ie, it requires that the functions are reentrant.

Most 'C' compilers achieve this by using the stack, so that their functions are inherently reentrant - Keil C51 does not do this and its functions are inherently not reentrant.

This is the same reason why Keil C51 has issues with function pointers - as previously explained: http://www.keil.com/forum/17469

Again, this is down to the specific features of the 8051 architecture and, again, you must not just assume that the 8051 is "just another processor" - it isn't!

 RE: A recursive function requires a stack for storing the return values

"It also requires some way to pass parameters & maintain local variables so that each "recursion" doesn't corrupt the data & parameters of previous recursions; ie, it requires that the functions are reentrant."

Not always needed. The "standard" recursive function fac() who every school uses as prime example of recursion can work inplace. A lot of linear recursive functions just needs one set of registers.

 RE: A recursive function requires a stack for storing the return values

to the OP

STOP what you are doing, read "the bible" get familiar with the architecture you are working with. You are trying to shoot down a 747 with a pellet gun.

Erik

here are the links to "the bible"
Chapter 1 - 80C51 Family Architecture:
http://www.nxp.com/acrobat_download2/various/80C51_FAM_ARCH_1.pdf

Chapter 2 - 80C51 Family Programmer’s Guide and Instruction Set:
http://www.nxp.com/acrobat_download2/various/80C51_FAM_PROG_GUIDE_1.pdf

Chapter 3 - 80C51 Family Hardware Description:
http://www.nxp.com/acrobat_download2/various/80C51_FAM_HARDWARE_1.pdf

 RE: A recursive function requires a stack for storing the return values

A pellet in the eye of the pilot may be quite efficient - but having underpowered weapons means it takes much more planning and skill to manage.

 RE: A recursive function requires a stack for storing the return values

I agree with the sage advice of the replys to this post but having said that, I must insist that recursion for the Keil C51 toolset does work well when you stay within it's limitations.
You can set the max depth of recursion. And you limit the registers used by passing a minimum set of parameters.
As posted, only registers R7 and R6 will be used to pass parameters. The pseudo stack is built "top down" in the Idata area. It's not difficult to see how much Idata area is used by the pseudo stack.
Bradford

 RE: A recursive function requires a stack for storing the return values

Keil C51 toolset does work well when you stay within it's limitations. and accept its achitecturally mandated inefficiencies.

Keil has, I am sure due to pressure fron the "C is C" types, implemented many functions that the architecture of the '51 makes extremely inefficient and likely to eat resources beyond what is available.

Sure, with a PC attitude, you can just implement all the inefficient code you want and then say "We need a faster peocessor"

Has anyone ever thought about the fact that while the greenies are constantly on the back of e.g. Dell, nobody complains when the next Microsoft wonder requires a much faster (and thus power hungry) computer.

Erik

 RE: A recursive function requires a stack for storing the return values

But recursion is a valid programming paradigm.

And a 8051 can support recursion.

No reason to not use recursion for cases where it gives an advantage. Finding examples of how a tool can be abused doesn't mean that a tool should never be used.

 RE: A recursive function requires a stack for storing the return values

No reason to not use recursion for cases where it gives an advantage. Finding examples of how a tool can be abused doesn't mean that a tool should never be used.

no argument.

The point is that if you do "C is C" and do not know the implications with the architecture, you have not taken the time to get to know the '51 aka "architectural ignorance".

There are, indeed cases where a careful use of one of the features that have been wrested into C51 can be justified, but doing so just because "C is C" is plain foolish.

Erik

 RE: A recursive function requires a stack for storing the return values

I kind of expect an embedded developer to be competent enough to:
1) Have a rough idea about mapping from C to assembler.
2) Be able to look at disassembly if expectations doesn't match reality.

 RE: The pseudo stack is built "top down" in the Idata area

This case is not one of them - especially on an 8051!

 RE: This case is not one of them - especially on an 8051!

Sorry - that post should have been titled, "use recursion for cases where it gives an advantage"

In other words: I agree that recursion may, in general, be used where it gives an advantage (within the limitations of the implementation) - but the example at hand is not one of them!

 RE: This case is not one of them - especially on an 8051!

Yes, this is a case of a linear problem that is trivial to rewrite as a loop. And as i noted earlier, the only state info the loop will need is one character/iteration since the loop produces the characters in the reverse order.

Another alternative so instead produce the output in correct order is to have a sequence of operations handling 10^4, 10^3, 10^2, ...

The recursive solution requires the return address for n iterations, and an unknown number of state bytes/iteration that will depend completely on compiler and optimization level. And how will the compiler know the maximum recursion depth?

 RE: The pseudo stack is built "top down" in the Idata area

It seems a very bad idea to put the "pseudo stack" into IDATA!

IDATA is only 128 or 256 bytes - and also has to accomodate the "real" hardware stack...

 RE: The pseudo stack is built "top down" in the Idata area

http://www.keil.com/support/man/docs/c51/c51_le_reentrantfuncs.htm

    * Small model reentrant functions simulate the reentrant stack in idata memory.
    * Compact model reentrant functions simulate the reentrant stack in pdata memory.
    * Large model reentrant functions simulate the reentrant stack in xdata memory.

 RE: The pseudo stack is built "top down" in the Idata area

Yes, I know it can be done; what I said was that I thought it was a bad idea to do it - for the reasons stated!

 RE: The pseudo stack is built "top down" in the Idata area

You are right. But in general I think, an unlimited recursion is a bad idea. In other case, the maximum size of the required stack is known.

 RE: The pseudo stack is built "top down" in the Idata area

I have used reentrant ,but the result always lack one charater. I want the result is '4','2','6','7', but the actual outcome is '4','2','6'.
the '7' disappears. why?

void
binary_to_ascii(unsigned int value reentrant

{

unsigned int quotient; quotient = value/10; if(quotient !=0 ) binary_to_ascii(quotient); putchar(value%10+'0');

}

int
main()
{ while(1){ binary_to_ascii(4267); }
}