473,320 Members | 2,180 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Really don't know how to use recursion

a
After several days struggling, I'm still unable to generate a string
automatically *ONE by ONE*. I don't want to create a long array memorizing
all the output strings and then traverse this array to print the content
out.

For example, for studying the frequency of 5-letter words composed of
{a,b,c,d,e} in a
string, the length of array of (aaaaa, aaaab,
...., caaaa, ..., eeeee) will then be 5*5*5*5*5.

Indeed what I want is to print aaaaa first, then aaaab, then aaaac, ...,
eeeea, eeeeb, ..., eeeee.

The problem is complicated by that I want to study n-letter words (the above
example, n=5).

So I try write something like:

char lookup(int lv, int idx) {
if (lv != 0)
lookup(lv-1, idx);

if (idx != 0)
lookup(lv, idx-1);

if (idx == 0) return 'a';
else if (idx == 1) return 'b';
else if (idx == 2) return 'c';
else if (idx == 3) return 'd';
else if (idx == 4) return 'e';
}

but indeed in this way I need to create the long array concatenating one by
one....

Please help :( I'm not asking for the whole codes but I really don't know
what direction I should go for to complete the seemingly automatic task.
Dec 25 '07 #1
3 1521
a wrote:
After several days struggling, I'm still unable to generate a string
automatically *ONE by ONE*. I don't want to create a long array memorizing
all the output strings and then traverse this array to print the content
out.

For example, for studying the frequency of 5-letter words composed of
{a,b,c,d,e} in a
string, the length of array of (aaaaa, aaaab,
..., caaaa, ..., eeeee) will then be 5*5*5*5*5.

Indeed what I want is to print aaaaa first, then aaaab, then aaaac, ...,
eeeea, eeeeb, ..., eeeee.

The problem is complicated by that I want to study n-letter words (the above
example, n=5).

So I try write something like:

char lookup(int lv, int idx) {
if (lv != 0)
lookup(lv-1, idx);

if (idx != 0)
lookup(lv, idx-1);

if (idx == 0) return 'a';
else if (idx == 1) return 'b';
else if (idx == 2) return 'c';
else if (idx == 3) return 'd';
else if (idx == 4) return 'e';
}
What is this function intended to do? Without a definition of what it
should do, there is no way to evaluate it, except to say that it is more
complicated than it needs to be to return its current result.

Regarding what you say you want, here is the definition of a function to help:

/* Function: NextPermutation
** Description: This function accepts an array containing a permutation of
** n integers 0 to m-1. It returns the next lexically higher
** permutation.
**
** Example: n = 3, m = 4, perm[] = {1,2,3,3}
** result: perm[] = {1,3,0,0}
*/
int /* 0: next permutation returned, 1: entry value was last */
NextPermutation (
unsigned char *perm, /* in: current permutation, each 0..(m-1),
** most significant element first,
** out: next permutation */
int n, /* number of elements in permutation */
int m /* number of values for each element */
);

The output can be mapped easily to lowercase letters (or anything else).
I have NOT written the function, that's your opportunity!

--
Thad
Dec 25 '07 #2
a

"Thad Smith" <Th*******@acm.orgwrote in message
news:47***********************@auth.newsreader.oct anews.com...
What is this function intended to do? Without a definition of what it
should do, there is no way to evaluate it, except to say that it is more
complicated than it needs to be to return its current result.

Regarding what you say you want, here is the definition of a function to
help:

/* Function: NextPermutation
** Description: This function accepts an array containing a permutation of
** n integers 0 to m-1. It returns the next lexically higher
** permutation.
**
** Example: n = 3, m = 4, perm[] = {1,2,3,3}
** result: perm[] = {1,3,0,0}
*/
int /* 0: next permutation returned, 1: entry value was last
*/
NextPermutation (
unsigned char *perm, /* in: current permutation, each 0..(m-1),
** most significant element first,
** out: next permutation */
int n, /* number of elements in permutation */
int m /* number of values for each element */
);

The output can be mapped easily to lowercase letters (or anything else).
I have NOT written the function, that's your opportunity!

--
Thad
After following your guidance and read posts from Google, I somehow solve
the problem when the word size <= character set size.

In the following code, when I set WSIZE chrssize, the program fails. Why
the for loop and recursion fails? I have set the list size large enough...

#include <stdio.h>

int WSIZE=2,chrssize=4;
char charList[20];
char chrs[]={'a','b','c','d'};

void permute(int start)
{
int i,j;
if(start==WSIZE)
{
for(i=0;i<WSIZE;i++)
printf("%c",charList[i]);
puts("");
}
else
{
i=start;
int k=0;
for(j=0;j<chrssize;j++)
{
charList[i]=chrs[k++];
permute(start+1);
}
}
}

main () {
permute(0);
}
Dec 26 '07 #3
a wrote:
"Thad Smith" <Th*******@acm.orgwrote in message
news:47***********************@auth.newsreader.oct anews.com...
>What is this function intended to do? Without a definition of what it
should do, there is no way to evaluate it, except to say that it is more
complicated than it needs to be to return its current result.

Regarding what you say you want, here is the definition of a function to
help:

/* Function: NextPermutation
** Description: This function accepts an array containing a permutation of
** n integers 0 to m-1. It returns the next lexically higher
** permutation.
**
** Example: n = 3, m = 4, perm[] = {1,2,3,3}
** result: perm[] = {1,3,0,0}
*/
int /* 0: next permutation returned, 1: entry value was last
*/
NextPermutation (
unsigned char *perm, /* in: current permutation, each 0..(m-1),
** most significant element first,
** out: next permutation */
int n, /* number of elements in permutation */
int m /* number of values for each element */
);

After following your guidance and read posts from Google, I somehow solve
the problem when the word size <= character set size.
You missed the essence of my post: explicitly define what your function does.
In the following code, when I set WSIZE chrssize, the program fails. Why
the for loop and recursion fails? I have set the list size large enough...

#include <stdio.h>

int WSIZE=2,chrssize=4;
char charList[20];
char chrs[]={'a','b','c','d'};

void permute(int start)
{
int i,j;
if(start==WSIZE)
{
for(i=0;i<WSIZE;i++)
printf("%c",charList[i]);
puts("");
}
else
{
i=start;
int k=0;
for(j=0;j<chrssize;j++)
{
charList[i]=chrs[k++];
permute(start+1);
}
}
}

main () {
permute(0);
}
It works for me, as long as chrssizze <= sizeof chrs and WSIZE <= sizeof
charList, after I made C90-compatible changes:
1. define main as int main(void) (also for C99)
2. place i=start; after int k=0;
3. added return 0; to the end of main.
--
Thad
Dec 26 '07 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Peri | last post by:
I'm trying to create Python parser/interpreter using ANTLR. Reading grammar from language refference I found: or_expr::= xor_expr | or_expr "|" xor_expr For me it looks like infinite recursion....
13
by: Roger B. | last post by:
Hello, I am working on a personal interest project and have been racking my brain on this problem for about 5 hours total now, and tracking through old newsgroup posts but haven't figuried it...
10
by: paulw | last post by:
Hi Please give problems that "HAS TO" to use recursion (recursive calls to itself.) Preferrably real world examples, not knights tour. I'm thinking about eliminating the use of stack... ...
2
by: Csaba Gabor | last post by:
I suppose spring fever has hit at alt.math.undergrad since I didn't get any rise from them when I posted this a week ago, so I am reposting this to some of my favorite programming groups: I'm...
75
by: Sathyaish | last post by:
Can every problem that has an iterative solution also be expressed in terms of a recursive solution? I tried one example, and am in the process of trying out more examples, increasing their...
10
by: MakeMineScotch | last post by:
What's the secret to writing recursive functions that won't crash the computer?
6
by: Andre Kempe | last post by:
hej folks. i have a heap with fixed size and want to determine the depth of a element with given index at compile-time. therefore i wrote some templates. however, when i use template...
20
by: athar.mirchi | last post by:
..plz define it.
35
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.