Tuesday, November 17, 2015

Digest for comp.lang.c++@googlegroups.com - 23 updates in 3 topics

Paul <pepstein5@gmail.com>: Nov 17 08:42AM -0800

Can anyone give me any guidelines, perhaps by giving a reference, on the general technique on translating recursive algorithms into iterative algorithms?
 
For example, the basic (inorder/ preorder/ postorder) traversals of binary trees are trivial to implement recursively. I've heard it said that these methods can be done iteratively using a stack, but I can't find it implemented anywhere.
 
Thank You,
 
Paul
scott@slp53.sl.home (Scott Lurndal): Nov 17 05:30PM

>Can anyone give me any guidelines, perhaps by giving a reference, on the general technique on translating recursive algorithms into iterative algorithms?
 
>For example, the basic (inorder/ preorder/ postorder) traversals of binary trees are trivial to implement recursively. I've heard it said that these methods can be done iteratively using a stack, but I can't find it implemented anywhere.
 
Recursion _is_ iteration using a stack.
 
Mimic it.
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Nov 17 07:44PM

On Tue, 17 Nov 2015 08:42:05 -0800 (PST)
> binary trees are trivial to implement recursively. I've heard it
> said that these methods can be done iteratively using a stack, but I
> can't find it implemented anywhere.
 
In the functional languages, iteration on the one hand traditionally
refers to recursion in tail position (where tail call elimination is
possible so it has effect as what would be a loop construct in
imperative languages), and recursion on the other hand refers to
recursion not in tail position. The first generally involves passing
intermediate accumulated results as an argument to the recursively
called function, and the second involves storing intermediate results
as return values on the call stack.
 
What the difference is in C++ is anyone's guess, because recursing in
tail position is difficult because of destructors/RTTI. In an
imperative language, do what suits them. That does not often involve
extensive recursion.
 
This is an introductory text from the functional standpoint:
https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 .
That may or may not be what you had in mind.
 
Chris
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Nov 17 07:50PM

On Tue, 17 Nov 2015 19:44:57 +0000
> as return values on the call stack.
 
> What the difference is in C++ is anyone's guess, because recursing in
> tail position is difficult because of destructors/RTTI.
^^^^^^^^^^RAII
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 18 12:22AM +0100

On 11/17/2015 5:42 PM, Paul wrote:
 
> For example, the basic (inorder/ preorder/ postorder) traversals of binary trees
> are trivial to implement recursively. I've heard it said that these methods can
> be done iteratively using a stack, but I can't find it implemented anywhere.
 
A recursive call corresponds to pushing a state on a stack. For the
mechanical translation of recursive calls to iterative code, as the
compiler does with C++ code, the state pushed includes a return address,
i.e. where to continue when that state is popped. For a simulation of
that in C++ I think it would be easiest to use case label values as
simulated return addresses, and to think of the rest of the state as the
current local variables' state, instead of as call arguments.
 
For more intelligent human level translation of recursive to iterative,
algorithm transformation, one may think instead of what sequence of
states the stack will hold at any time.
 
* * *
 
As a first example consider Euclid's greatest common divisor algorithm:
 
auto gcd1( int const a, int const b )
-> int
{ return (b == 0? a : gcd1( b, a%b )); }
 
The idea is simply that if a>b, then either b is the greatest common
divisor D, or else, since there's a whole number of D's in b, and then
further a whole number of D's in a-b, D must be the common divisor of
a-b and b. And to avoid the inefficiency of Euclid's repeated
subtraction, we just reduce that immediately to a%b and b.
 
The recursive call pushes a pair of numbers on a stack, so you can
translate it like this:
 
using Pair = pair<int, int>;
 
auto gcd2( int const a, int const b )
-> int
{
stack<Pair> s;
s.push( Pair{ a, b } );
for( ;; )
{
Pair const current = s.top();
s.pop();
if( current.second == 0 ) { return current.first; }
s.push( Pair{ current.second, current.first%current.second } );
}
}
 
In this code the stack will never have more than one item, so it can be
replaced with a single variable:
 
auto gcd3( int const a, int const b )
-> int
{
Pair current = {a, b};
for( ;; )
{
if( current.second == 0 ) { return current.first; }
current = Pair( current.second, current.first%current.second );
}
}
 
And then there are a number of further trivial simplifications, which I
leave to you.
 
* * *
 
With the basics covered, let's do an inorder traversal of a binary tree:
 
void display1( Node const* const root )
{
if( root == nullptr ) { return; }
display1( root->left );
cout << root->value << ' ';
display1( root->right );
}
 
Each recursive call pushes a pointer onto a stack. Expressing both
recursive calls as iteration is difficult to do immediately. But the
first recursive call is not so difficult:
 
void display2( Node const* const root )
{
stack<Node const*> s;
Node const* p = root;
while( p != nullptr )
{
s.push( p );
p = p->left;
}
while( not s.empty() )
{
Node const* const current = s.top();
s.pop();
cout << current->value << ' ';
display2( current->right );
}
}
 
The idea here is to display the left subtree plus the root node, with
the help of the single remaining recursive call, and then to let that
call also handle the right subtree.
 
Now for the remaining recursive call, it clearly pushes the right child
node pointer onto the stack, and then proceeds left again:
 
void display3( Node const* const root )
{
stack<Node const*> s;
Node const* p = root;
while( p != nullptr )
{
s.push( p );
p = p->left;
}
while( not s.empty() )
{
Node const* const current = s.top();
s.pop();
cout << current->value << ' ';
Node const* p = current->right;
while( p != nullptr )
{
s.push( p );
p = p->left;
}
}
}
 
But at least for me it's not entirely obvious at a glance that this
should work, so I tested it with a little 7-node tree. Disclaimer: there
may be bugs still. But it worked with that tree.
 
Now, this code has the form of an unrolled LOOP-AND-A-HALF, so, roll
that loop back up:
 
void display4( Node const* const root )
{
stack<Node const*> s;
Node const* p = root;
for( ;; )
{
while( p != nullptr )
{
s.push( p );
p = p->left;
}
if( s.empty() )
{
return;
}
Node const* const current = s.top();
s.pop();
cout << current->value << ' ';
p = current->right;
}
}
 
Some further simplifications may be possible but, again, I leave that to
you.
 
* * *
 
Typically a problem either fits a recursive or an iterative form. GCD is
an exception, it's just about equally well expressed as recursive or
iterative (I suspect this holds in general for any tail-recursive
function, that it's just about equally as clear when expressed
iteratively). But the in-order traversal above is much more clear to me
as recursive function than as iterative. And this should IMO be the main
consideration. Not whether one can possibly shave off a nanosecond or
two, but which approach yields the most clear and easiest to understand
code.
 
 
Cheers & hth.,
 
- Alf
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 18 12:26AM +0100

On 11/18/2015 12:22 AM, Alf P. Steinbach wrote:
> [code]
 
Sorry for writing both Pair{a,b} and Pair(a,b). I started with a simple
struct, requiring {}, then changed that to a typedef of std::pair.
Imperfect, yes.
 
Cheers,
 
- Alf
"Tobias Müller" <troplin@bluewin.ch>: Nov 17 10:26PM

> this thread:
 
> "And generally, I find it better to declare things before
> they're used."
 
How do you "use" private data members in a public member function
*declaration*?
 
You can only use private data members in a member function *definition*.
And those are usually outside of the class definition body.
 
Tobi
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 17 11:49PM +0100

On 11/17/2015 11:26 PM, Tobias Müller wrote:
> *declaration*?
 
> You can only use private data members in a member function *definition*.
> And those are usually outside of the class definition body.
 
I think it's a good idea to use a single convention instead of multiple
conventions, when it's practical to use a single one.
 
The convention of placing data members up top covers the case of having
definition before use where the data members are used in an in-class
function definition, whether that function is member or friend.
 
The convention of placing data members last doesn't cover that case.
 
 
Cheers & hth.,
 
- Alf
Vlad from Moscow <vlad.moscow@mail.ru>: Nov 17 08:06AM -0800

On Tuesday, November 17, 2015 at 6:53:40 PM UTC+3, Wouter van Ooijen wrote:
 
> That being your analysis of the sitution, I don't get why would you want
> to be on it?? Do you want to support a facist website?
 
> Wouter
 
I am not supporting a fascist site. Otherwise I would not create this thread.
 
I am supporting programmers all over the world.
Geoff <geoff@invalid.invalid>: Nov 17 09:30AM -0800

On Tue, 17 Nov 2015 05:46:53 -0800 (PST), Vlad from Moscow
 
>My code does not compare string "aprilaaaa".
>It simply unable to except such a string because
>its character array declared as having 6 characters.:)
 
This is precisely why your code is flawed. It compares a 5 character
array with the first 5 characters of the input string. Since the
implied intent of the code is a password check, your failure to
recognize the extra characters as invalid input makes the code
insecure.
 
This is kind of error, along with the unacceptable initialization of
the "april" string makes your answer incorrect and is the error of a
novice programmer who doesn't understand C strings and how to
initialize them. This error in your code is what got you the first
down votes. Your arrogant response is what got your account suspended.
Geoff <geoff@invalid.invalid>: Nov 17 09:42AM -0800

On Tue, 17 Nov 2015 06:30:58 -0800 (PST), Vlad from Moscow
 
>The program compares a string of 6 characters with the given character array. And the program is doing it corredctly.
 
>Moreover the input stream can contain megabytes of data. It can be even a stream connected to a file.
 
It is absolutely impossible for the code of the OP and your own code
to be connected to a stream of any kind. Why? int main( void )
You accept no arguments in your own code. Therefore the code, as you
yourself wrote it, cannot be coupled to a stream.
 
The original question was "I have a _program_ that has a key to open".
It doesn't say file, it doesn't say stream.
 
Your answer is a failure.
 
Q.E.D.
 
The original code as posted by the original questioner:
 
I want to make a program that has a key to open. But when i comparing
the key and the input, it always says "Wrong":
 
#include <stdio.h>
 
int main(){
char key[5]="april",ckey[5];
printf("Enter the key: ");
scanf("%s",ckey);
if(ckey==key){
printf("Correct.");
}
else{
printf("Wrong.");
}
return 0;
}
 
 
Your code as it currently exists in answer to the question:
 
#include <stdio.h>
 
int main( void ){
char key[5]="april",ckey[6];
printf("Enter the key: ");
scanf("%5s",ckey);
 
size_t i = 0;
 
while ( i < sizeof( key ) && key[i] == ckey[i] ) ++i;
 
if( i == sizeof( key ) ){
printf("Correct.");
}
else{
printf("Wrong.");
}
return 0;
}
Vlad from Moscow <vlad.moscow@mail.ru>: Nov 17 09:57AM -0800

On Tuesday, November 17, 2015 at 8:42:33 PM UTC+3, Geoff wrote:
> }
> return 0;
> }
 
 
Don't disgrace yourself even more. We all already know that you are a beginner that knows neither C nor C++.:)
Vlad from Moscow <vlad.moscow@mail.ru>: Nov 17 10:01AM -0800

On Tuesday, November 17, 2015 at 8:30:30 PM UTC+3, Geoff wrote:
> novice programmer who doesn't understand C strings and how to
> initialize them. This error in your code is what got you the first
> down votes. Your arrogant response is what got your account suspended.
 
Could you explain how a character array containing a string at most of length equal to 5 can have extra characters?:)
Geoff <geoff@invalid.invalid>: Nov 17 10:05AM -0800

On Tue, 17 Nov 2015 09:57:08 -0800 (PST), Vlad from Moscow
<vlad.moscow@mail.ru> wrote:
 
[nothing responsive on the issues]
 
Ah, now you are merely a troll.
Geoff <geoff@invalid.invalid>: Nov 17 10:16AM -0800

On Tue, 17 Nov 2015 10:01:37 -0800 (PST), Vlad from Moscow
>> down votes. Your arrogant response is what got your account suspended.
 
>Could you explain how a character array containing
>a string at most of length equal to 5 can have extra characters?:)
 
 
The intent of the program is a string match, not a string containing a
match. The program is intended to return "Correct" when the user types
in a string exactly matching "april", not a string containing april.
 
Your solution fails to meet the specified criteria.
 
I say again, the confusion of the OP about proper initialization of
the key array has made you commit a novice error of thinking that when
the OP wrote char key[5] = "april" he knew what he was doing. I assert
that he's a complete novice and the initialization should have been
char key[] = "april", erasing any doubt about whether key is a C
string or not.
 
If the OP wasn't a novice he wouldn't have used the term "strings" in
his title and if he had intended the array be strictly an array of
characters he would have chosen to write
 
char key[5] = {'a', 'p', 'r', 'i', 'l'}
 
and removed all doubt.
 
His code was erroneous for implementation of his stated intent.
Your answer was erroneous because you assumed the code was more
correct than the stated intent.
Geoff <geoff@invalid.invalid>: Nov 17 10:23AM -0800

On Tue, 17 Nov 2015 10:16:45 -0800, Geoff <geoff@invalid.invalid>
wrote:
 
 
>His code was erroneous for implementation of his stated intent.
>Your answer was erroneous because you assumed the code was more
>correct than the stated intent.
 
It is precisely these kinds of errors:
 
char key[5] = "april";
 
that leads to this triggering an error in C++.
Vlad from Moscow <vlad.moscow@mail.ru>: Nov 17 10:41AM -0800

On Tuesday, November 17, 2015 at 9:24:04 PM UTC+3, Geoff wrote:
 
> It is precisely these kinds of errors:
 
> char key[5] = "april";
 
> that leads to this triggering an error in C++.
 
And what?! Are you an adequate person?
 
From the very beginning here was said that it is a C code.
 
And moreover in my answer at SO there is explicitly written that such an initialization is valid in C and not valid in C++.
Ian Collins <ian-news@hotmail.com>: Nov 18 08:23AM +1300

Vlad from Moscow wrote:
 
> From the very beginning here was said that it is a C code.
 
So why did you post hare and not to a C group?
 
Oh wait, the ++ didn't fit in your buffer....
 
--
Ian Collins
Ian Collins <ian-news@hotmail.com>: Nov 18 08:24AM +1300

Vlad from Moscow wrote:
 
>> What part of "I just copied the source code from YOUR Stackoverflow
>> answer" are you having trouble comprehending?
 
> Are you an assistant of the Stackoverflow? Or are you both swindlers?:)
 
Who knows, but it's pretty clear that you are an arse.
 
Plonk.
 
--
Ian Collins
Geoff <geoff@invalid.invalid>: Nov 17 11:38AM -0800

On Tue, 17 Nov 2015 10:41:40 -0800 (PST), Vlad from Moscow
 
>From the very beginning here was said that it is a C code.
 
Then why are you complaining about your problems with the SO site in a
C++ newsgroup?
 
>And moreover in my answer at SO there is explicitly
>written that such an initialization is valid in C and
>not valid in C++.
 
While it is syntactically correct C, it is very poor C in practice and
anyone teaching or writing such poor C should be shown how to do it
correctly and one should not validate such code as you have done. This
is why it's an error in C++ and why I showed how to do it correctly in
C++ and C.
 
I showed you:
1. A correct C program handling strings as specified.
2. An exact match return, not just a containing string match.
3. Proper use of the strcmp library function instead of the
erroneous if(key == ckey) which the OP presented as his
problematic code.
4. A correct C++ program that correctly uses class string and proper
console input technique.
5. A C++ program that uses == on class string objects for comparison
of strings.
6. Both C and C++ programs return "Correct" on exact match of the
strings and "Wrong" when the match is not exact.
7. Programs given were used to handle strings as defined in the
question and not to perpetuate erroneous concepts expressed in
problematic code by someone who is clearly a novice and having
difficulty with the concepts of strings in C and how to
manipulate them.
Vlad from Moscow <vlad.moscow@mail.ru>: Nov 17 12:13PM -0800

On Tuesday, November 17, 2015 at 10:38:42 PM UTC+3, Geoff wrote:
> problematic code by someone who is clearly a novice and having
> difficulty with the concepts of strings in C and how to
> manipulate them.
 
 
You showed only one thing that you are a low-qualified programmer that is slow of understanding and nothing more.:)
 
Bye.
Geoff <geoff@invalid.invalid>: Nov 17 12:33PM -0800

On Tue, 17 Nov 2015 12:13:04 -0800 (PST), Vlad from Moscow
 
>You showed only one thing that you are a low-qualified
>programmer that is slow of understanding and nothing more.:)
 
You have shown that you are a troll and your ban on SO was
well-deserved and needs to be permanent.
 
Goodbye.
Vir Campestris <vir.campestris@invalid.invalid>: Nov 17 09:38PM

On 17/11/2015 15:03, Chris Vine wrote:
> it is "fascist", which is a ridiculous description of a website anyway,
> nor because you are Russian, but because you are a complete and utter
> dick with personality and anger-management issues.
 
I don't think I'd have put it _quite_ like that - but that's close enough.
 
Andy
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)