470,833 Members | 1,952 Online

# Recursion Basics

The Problem is CFG grammar generation
Eg:
Input S->ABC
A->bcd
B->efg
C->hij
It should produce the o/p bcdefghij substituting for every Capitals
found on the way recursively

The C pgm I wrote was:
#include<stdio.h>
#include<conio.h>
int main()
{
int recurPrint(char[15],char[][50],int,int);
int findVar(char,char[]);
char stack[50];
char grmr[15][50];
char lhs[15],ch;
int i=0;
clrscr();
while(1)
{
printf("\n Enter variable:");
scanf("%c",&lhs[i]);
flushall();
printf("\n Enter production:");
gets(grmr[i]);

printf("\n Do you want to continue[y/n]:");
ch=getche();
if(ch=='n'||ch=='N')
break;
++i;
}

lhs[i+1]='\0';

recurPrint(lhs,grmr,0,0);

getche();
return 0;

}
int findVar(char find,char lhs[])
{
int i=0;
while(lhs[i]!='\0')
{
if(lhs[i]==find)
return i;
++i;
}

}

int recurPrint(char lhs[],char grmr[][50],int lims,int ji)
{
static int index;
static int j;
index=lims;
j=ji;
printf("\n Start of function Rep");
printf("\n Index is:%d",index);
printf("\n With j is:%d",j);
getche();
if(grmr[index][j]=='\0')
return 0;
else if(grmr[index][j]>='A' && grmr[index][j]<='Z')
{
printf("\n Capital arrived");
getche();
index=findVar(grmr[index][j],lhs);
recurPrint(lhs,grmr,index,0);
}
else if(grmr[index][j]>='a' && grmr[index][j]<='z')
{
printf("\n Small arrived with j as:%d",j);
getche();
printf("%c",grmr[index][j]);
j++;
recurPrint(lhs,grmr,index,j);
}
}

The O/P I am getting for the input mentioned above is :
Start of function Rep
Index is:0
With j is:0
Capital arrived
Start of function Rep
Index is:1
With j is:0
Small arrived with j as:0 b
Start of function Rep
Index is:1
With j is:1
Small arrived with j as:1 c
Start of function Rep
Index is:1
With j is:2
Small arrived with j as:2 d
Start of function Rep
Index is:1
With j is:3

Jun 27 '08 #1
8 1400
smartbeginner said:
The Problem is CFG grammar generation
The problem may actually be running before you can walk.

<snip>
gets(grmr[i]);
Until you've understood why this line is stupid, there isn't a lot of point
in discussing any other part of your program - which is a shame, because
it sounds like you've got a fun problem.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Jun 27 '08 #2
On Sun, 13 Apr 2008 08:00:38 -0700 (PDT), smartbeginner
<rr******@gmail.comwrote:
>The Problem is CFG grammar generation
Eg:
Input S->ABC
A->bcd
B->efg
C->hij
It should produce the o/p bcdefghij substituting for every Capitals
found on the way recursively

The C pgm I wrote was:
#include<stdio.h>
#include<conio.h>
To maximize the chances of getting help here, it is best to restrict
your code to standard C. Not all of us have this non-standard header
and for those that do it may not contain the same code as yours.
>int main()
{
int recurPrint(char[15],char[][50],int,int);
int findVar(char,char[]);
Because these declarations are inside main, they go out of scope at
the end of main.
char stack[50];
char grmr[15][50];
char lhs[15],ch;
int i=0;
clrscr();
This serves no purpose. Many here have voiced the opinion that your
code should not decide whether previous information on my screen is
still useful.
while(1)
{
printf("\n Enter variable:");
Due to the lack of a terminating \n, on some systems this prompt may
not appear until the buffer is flushed. You are left with the system
expecting input and the user confused.
scanf("%c",&lhs[i]);
flushall();
A non-standard function.
printf("\n Enter production:");
gets(grmr[i]);
How do you propose to prevent buffer overflow?
>
printf("\n Do you want to continue[y/n]:");
ch=getche();
A non-standard function
if(ch=='n'||ch=='N')
break;
++i;
}
How do you prevent the user from inputting more than 15 strings?
>
lhs[i+1]='\0';
If the user stops after the 15th string, this will invoke undefined
behavior by attempting to set the non-existent object lhs[15].
>
recurPrint(lhs,grmr,0,0);

getche();
return 0;

}
int findVar(char find,char lhs[])
The only reason recurPrint can recognize findVar as a declared
function is because the definition happens to precede the call. You
should move the declarations out of main and place them at file scope.
{
int i=0;
while(lhs[i]!='\0')
{
if(lhs[i]==find)
return i;
++i;
}
If you reach this point in the code, the function will return without
returning an int. This invokes undefined behavior.
>

}

int recurPrint(char lhs[],char grmr[][50],int lims,int ji)
{
static int index;
static int j;
index=lims;
j=ji;
printf("\n Start of function Rep");
printf("\n Index is:%d",index);
printf("\n With j is:%d",j);
getche();
if(grmr[index][j]=='\0')
return 0;
else if(grmr[index][j]>='A' && grmr[index][j]<='Z')
Not all character systems make the letters consecutive. Look at the
isupper function to perform this test.
> {
printf("\n Capital arrived");
getche();
Is it really your intention to have the user press a key for every
letter being printed?
> index=findVar(grmr[index][j],lhs);
You never check if findVar succeeded.
> recurPrint(lhs,grmr,index,0);
When this incarnation finally returns (after printing bcd), index is 0
and j is 0. j never gets incremented and you fall out of the
function. You never process the B. Either this block must include
some kind of loop or the calling statement in main needs to iterate
through the desired values of j.
> }
else if(grmr[index][j]>='a' && grmr[index][j]<='z')
islower. But then, that prevents the expansion from including any
non-alpha characters, such as numbers. Why not just else?
> {
printf("\n Small arrived with j as:%d",j);
getche();
printf("%c",grmr[index][j]);
j++;
recurPrint(lhs,grmr,index,j);
}
Your code definitely reaches this point yet you fail to return the
promised int. This invokes undefined behavior.
}

The O/P I am getting for the input mentioned above is :
Start of function Rep
Index is:0
With j is:0
Capital arrived
Start of function Rep
Index is:1
With j is:0
Small arrived with j as:0 b
Start of function Rep
Index is:1
With j is:1
Small arrived with j as:1 c
Start of function Rep
Index is:1
With j is:2
Small arrived with j as:2 d
Start of function Rep
Index is:1
With j is:3

See the logic error identified in the capitals block.
Remove del for email
Jun 27 '08 #3
Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.
Thats in the recursion function.
Regarding the findVar() funtion:suppose all grammar given and it
correctly returns the value.
Just figure out what should i do in my algorithm for realising the
problem.
The recursion pattern i identified is :
S=ABC giving way to A->bcd and then returning to S=ABC fn and then
checking for B then to B=efg and then returning back to S=ABC's C part
and then to C=hij and finally falling out.

I guess problem is regarding the value of index i am using and its not
properly understood on returning from function.
Is this can be solved using static variables and all.

Jun 27 '08 #4
smartbeginner said:
Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.
Thats in the recursion function.
No, *several* of your problems are in the recursion function, and Barry
pointed out a lot that aren't. They all need to be fixed if your code is
to work satisfactorily. Start by fixing all the problems Barry mentioned.
Even if those fixes don't cumulatively solve your problem (which is not
impossible - it has sometimes happened that way), they will make your code
clearer, simpler, more correct, more robust, and less likely to distract
clcers from finding the problem that you want them to find.
Is this can be solved using static variables and all.
I was once asked to help a colleague who was struggling with a recursive
function (actually a FindFirstFile/FindNextFile thing), with which he had
a reproducible problem. I had told him "no file scope objects AT ALL, and
no static objects if there is any sensible way to avoid them". Anyway, I
wandered over to check his code, and pointed immediately to the file scope
object. I asked "What's that doing there?" He said "Oh, I know you hate
globals, but it's just temporary - I'll get rid of it when I've got the
code working". I took the keyboard, shifted the "temporary" file scope
object inside his function, saved it, set the compiler going, and then
gave the keyboard back. "Now, show me this problem you're having." But my
colleague could no longer reproduce the problem, because the problem no
longer existed.

No file scope objects AT ALL[1], and no static objects if there is any
sensible way to avoid them.

[1] Some rules are made so that you THINK before you break them. This is
one such, but not one that should be broken casually.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Jun 27 '08 #5
smartbeginner wrote:
>
Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem. ... snip ...
This makes no sense whatsoever. See the sig. below.

--
If you want to post a followup via groups.google.com, ensure
you quote enough for the article to make sense. Google is only
an interface to Usenet; it's not Usenet itself. Don't assume
** Posted from http://www.teranews.com **
Jun 27 '08 #6
smartbeginner <rr******@gmail.comwrites:
Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.
I don't know that system, but let me give you another reason why
standard C is better. When I am testing a program I don't want to
have to keep typing at it. I want to put the input into a file like
this:

S->ABC
A->def
B->ghi
D->jkl

so I can test it simply by running:

%my-program <test-data

Not only is that easier, but so is the input:

while (i < 14 && scanf("%c->%49s\n", &lhs[i], grmr[i]) == 2) i++;

This is short, relatively clear, tests that the input actually worked
and won't read too many inputs nor overrun any buffers. I count 6
reasons to do it this way.
Thats in the recursion function.
Yes. It is trying to do too much. You are trying to recurse over j
(the string index) *and* into rules when you see a capital letter.
You don't need to use recursion for j. Just use it when you need to
"descend" into a rule.
Regarding the findVar() funtion:suppose all grammar given and it
correctly returns the value.
It takes longer to type this than to add "return -1;" to the function.
Just figure out what should i do in my algorithm for realising the
problem.
The recursion pattern i identified is :
S=ABC giving way to A->bcd and then returning to S=ABC fn and then
checking for B then to B=efg and then returning back to S=ABC's C part
and then to C=hij and finally falling out.
That's good but it is not what you are doing. Loop over the
characters on the right-hand-side (grmr[i]) rather than trying to
re-use the recursion. It will be simpler to get right.

--
Ben.
Jun 27 '08 #7
On Apr 14, 4:48 pm, Ben Bacarisse <ben.use...@bsb.me.ukwrote:
smartbeginner <rrohi...@gmail.comwrites:
Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.

I don't know that system, but let me give you another reason why
standard C is better. When I am testing a program I don't want to
have to keep typing at it. I want to put the input into a file like
this:

S->ABC
A->def
B->ghi
D->jkl

so I can test it simply by running:

%my-program <test-data

Not only is that easier, but so is the input:

while (i < 14 && scanf("%c->%49s\n", &lhs[i], grmr[i]) == 2) i++;

This is short, relatively clear, tests that the input actually worked
and won't read too many inputs nor overrun any buffers. I count 6
reasons to do it this way.
Thats in the recursion function.

Yes. It is trying to do too much. You are trying to recurse over j
(the string index) *and* into rules when you see a capital letter.
You don't need to use recursion for j. Just use it when you need to
"descend" into a rule.
Regarding the findVar() funtion:suppose all grammar given and it
correctly returns the value.

It takes longer to type this than to add "return -1;" to the function.
Just figure out what should i do in my algorithm for realising the
problem.
The recursion pattern i identified is :
S=ABC giving way to A->bcd and then returning to S=ABC fn and then
checking for B then to B=efg and then returning back to S=ABC's C part
and then to C=hij and finally falling out.

That's good but it is not what you are doing. Loop over the
characters on the right-hand-side (grmr[i]) rather than trying to
re-use the recursion. It will be simpler to get right.

--
Ben.
------------
Then how can I correct this.Why you said i am reusing the recursion?
Jun 27 '08 #8
sm*********@gmail.com writes:
<snip>
On Apr 14, 4:48 pm, Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>That's good but it is not what you are doing. Loop over the
characters on the right-hand-side (grmr[i]) rather than trying to
re-use the recursion. It will be simpler to get right.

--
Ben.
Best not to quote sigs (the part including and after the "-- ")
Then how can I correct this.Why you said i am reusing the recursion?
I don't know who to put it any clearer than the above without writing it
for you (which I don't really want to do). In the recursive function,
use a loop to look at every character. If it is a cap. look it up and
recurse.

--
Ben.
Jun 27 '08 #9

### This discussion thread is closed

Replies have been disabled for this discussion.