# C++/help plz

Question
hi
i wrote a simple code for ackerman function but it cant work when 'n' or 'm' is greater than 3 can you help me why it doesnt work?

#include<stdio.h>
int A(int m,int n);
void main(){
int m,n;
printf("Enter m & n :\n");
scanf("%d%d",&m,&n);
printf("m=%d   n=%d\n",m,n);
A(m,n);
printf("Result=%d\n",A(m,n));
}
int A(int m,int n){
if(m==0)
return n+1;
else if(n==0)
return A(m-1,1);
else if(m>0&&n>0)
return A(m-1,A(m,n-1));
}

thanx
Bita

Sorry but I do not have the time to reverse engineer, debug and possibly fix your code. You should be able to do this yourself.

However my initial thoughts are that I suspect this is another case of badly implemented recursion or that you failed to account for some part of the specification or behaviour of the Ackermann function (which I am unfamiliar with). I might make a better guess if you mentioned how your function/program "cant work" if m or n > 3.

As I seem to remember that I have already helped you with similar problems in the past you should be able to sort this out for yourself.

I suggest you start by double checking very carefully your implementation of the Ackermann function against the definition (e.g. as described at http://en.wikipedia.org/wiki/Ackermann_function). Remember int types are _signed_ types and can therefore be negative.

I would also think that _reading_ the description of the definition and behaviour of this function would give some _huge_ clues as to potential areas for problems. My very quick look revealed the following for starters:

"The Ackermann function is defined recursively for non-negative integers m and n"

If it is only meant to work with non-negative values maybe consider using unsigned int instead of int?

"Its value grows rapidly; even for small inputs, for example A(4,2) contains 19,729 decimal digits"

If the above is true then you have failed (again) to account for the finite nature of digital computers and the types they work with. Those 19,729 decimal digits would require 65,539 bits to store (or 8193 bytes). If you wish to use functions that produce such large values then maybe you should, as I have previously suggested, look into using big number libraries. Although I would suspect that you might also require a rather long time to process such a potentially large set of recursive function calls.

[Note:
I am unsure of the sort of behaviour of the function in this respect with only such a brief look at the definition - I would need to sit down and think it through more - something I think is really your job not mine. But as far as I can see the actual terminating case only ever increases n by 1, and so building such a large number would I guess take quite a few calls. Function calls (like all program operations), are not free in time, and in fact require setting up, jumping to and returing from. Thus recursion is therefore not that efficient especially in imperative languages like C and C++ for which iteration is an alternative to recursion (compare with functional languages for which recursion is the only option, and so they tend to optimise recursion).
-- end note].

So in your current implementation it looks like some of the values returned from the Ackermann function will not fit into an int or unsigned int and so the returned values will at some point (probably many points) overflow. It may also be that some combinations cause underflow to the parameters - especially if the implementation is operating outside its parameters due to unhandled overflow conditions.

If you do _not_ detect overflow or underflow and either occurs then finite binary values 'wrap' around - and so the values of the returned value and/or m and/or n then become meaningless and the continued functioning of your function invalid. You can detect overflow and underflow by comparing the result with the operand(s). For example:

Say result = n + 1; if after the calculation result < n then you have an overflow situation.
Say result = n - 1; if after the calculation result > n then you have an underflow situation.

[Note
Not handling overflow/underflow (which may occur in all manner of ways) appropriately is a real problem and has been the cause of some catastrophic failures, see for example the case of the ESA's Ariane 5 rocket disaster on the 4th June 1996 - http://www.cs.clemson.edu/~steve/Spiro/arianesiam.htm.
--end note]

If ensuring your implementation is correct and either uses an integer type that can handle the extremely large values and/or adding overflow/underflow handling does not help and fix the problem(s) then next I would "dry run" your code - i.e. execute it yourself plugging in values that fail and follow the program flow and track the values by hand. If you have a debugger available and know how to use it and how to build your code for use with the debugger then you could step through the code using a debugger. Of course with very large numbers of operations to produce a result this is going to take a very long time, so you may need to get creative and/or learn to use (the more advanced features of) a debugger <g>!

This is all I would do and as its your code I think you can do it just as well as I could, and you should have the advantage in that you should know what the expected results and behaviours are.

I shall re-iterate that point: you _should_ have understanding of the functions you are implementing, their complexity and the expected range of values they are to produce for given inputs and use types appropriate for these values. You _have_ to be able to debug and fix the code you create. Writing code and then asking someone else to make it work is not really on. Get used to using such techniques - we all do for the code we write (in fact writing the test code - unit tests - for a module of code often takes as much if not more time than writing the code itself). Of course in the professional development sphere you might well end up fixing code you did not write - but in such cases you hope to be paid for the time, or you are specifically contributing to say an open source project. In any case you would expect that the original creator of the code would have at least fixed the obvious/initial problems with the code.

Also, just a small point: it seems that you are writing C rather than C++ and I am a C++ expert...although I think it is fairly irrelevant in this particular case <g>!

C++

Volunteer

#### Ralph McArdell

##### Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

##### Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials