I need some help dealing with C++ and recursion

Question

tastybrownies 0 Newbie Poster

14 Years Ago

Hey everyone, I am pretty new to writing procedures that deal with this idea of recursion. I am trying to get into that certain frame of mind but I am having a little bit of trouble at the last minute. My goal was to implement a text operation called swap substring using recursion.

This is what I have so far:

procedure_body Swap_Substring (
	alters Text& t1,
	preserves Integer pos,
	preserves Integer len,
	alters Text& t2
    )
{
    //first impelementation of recursion of swap_sub_string, beginning
    //starting at t2.
    object Character ch, ch2;
    if(t2.Length() >0)
    {

        debug("t1 = " << t1 << "t2 = " << t2 << "pos = " << pos << "len=" << len << '\n');
        if(len > 0)
        {
	    t1.Remove(pos, ch);
	    t2.Remove(0, ch2);
	    Swap_Substring(t1,pos, len-1, t2);
	}

	if(len > 0)
	{
	    t2.Add(0, ch);
	    t1.Add(pos, ch2);
	}

    }
    else if(t2.Length() == 0)
    {
	if(len > 0)
	{

	    t1.Remove(pos, ch);
	    Swap_Substring(t1, pos, len -1, t2);
	    t2.Add(0, ch);
	}
    }
}

I'm sure some have noticed this is not straight C++. This is effectively C++ with a designated framework I have to use for university work. Any correct C++ would probably compile though. The object of this program is to swap a sub string, like so:

t1 = smile
pos = 1(where to start)
len = 2(letters to take out)
t2 = hey(to be swapped in)

so it should be
t1 = sheyle
pos = 1
len = 2
t2 = mi

My code is ALMOST close to working completely, it looks like I'm just off by a letter.

SAMPLE OF MY INPUT AND OUTPUT:
t1 = runner
pos = 2
len = 2
t2 = zee

correct output:
t1 = ruzeeer
pos = 2
len = 2
t2 = nn

my output:
t1 = ruzeer
pos = 2
len = 2
t2 = nne

See what I mean. It's like it's one letter away. This is probably some silly error, but for the life of me I can't find it after searching hours. I would GREATLY appreciate it if anyone could help me.

Thank you and have a good evening.

c++ recursion

3 Contributors
5 Replies
256 Views
13 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by Member #908245

Dani AI

Generated 8 Months Ago

Most likely cause: control-flow/order-of-operations and a missing “drain” case. The swap must preserve a clear invariant on every call: the total number of characters (t1.Length + t2.Length) stays constant, and each activation either (A) consumes one char from both strings, (B) consumes one from t1 only (because t2 is empty), or (C) moves remaining chars from t2 into t1 once len reaches zero. If any of those three behaviours is handled inconsistently the stack will reinsert characters in the wrong order and produce the “one letter off” symptom seen by .

Correct recursive structure (conceptual):

If len > 0 and t2 not empty: remove t1[pos] into ch1 and remove t2[0] into ch2, recurse with len-1, then after return add ch2 back into t1 at pos and add ch1 back into front of t2. This keeps relative order.
If len > 0 and t2 is empty: remove t1[pos] into ch1, recurse with len-1, then add ch1 to front of t2 (no insertion into t1).
If len == 0 and t2 not empty: remove t2[0] into ch2, recurse with len==0, then add ch2 into t1 at pos. Repeat until t2 is exhausted.

Debugging tips that quickly expose the bug:

Add a per-call trace of (len, pos, ch1, ch2, t1, t2) before and after the recursive call. Compare the pre/post snapshots to spot where a character is dropped or duplicated.

Assert the length invariant at each entry to narrow where the total count changes:

// capture before the first call
int total = t1.Length() + t2.Length();
// inside Swap_Substring at top of each call
assert(t1.Length() + t2.Length() == total);

Try the cases suggested by (t2 longer than needed) and the reverse (t2 shorter than len). Those reveal whether the drain case or the len==0 insertion case is missing.

Both ’s fix (explicit len==0 handling that drains t2 into t1) and ’s non-recursive substr approach are useful: the former keeps the recursive idea correct, the latter is the simplest practical solution if recursion isn’t required by the assignment.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

L0s3r 0 Newbie Poster · Answer 1 · 2012-02-21T10:12:01+00:00

My first qs. is what does Add and Remove function do.
2nd Qs. : Why you are using recursion specifically.

======================================================

Try for:

t1 = runner
pos = 2
len = 2
t2 = zeennaabbcc

You will get your mistake.

tastybrownies 0 Newbie Poster · Answer 2 · 2012-02-21T10:21:48+00:00

My first qs. is what does Add and Remove function do.
2nd Qs. : Why you are using recursion specifically.

The add function adds characters to a word and the remove function removes characters.

For example,

t1 = runner

t1.Add(the position of where you want to add the character, this holds the character that is intended to be added). So, if we say

ch = 'h'
t1.Add(0, ch); ======== hrunner, or t1.Add(2, ch); ========ruhnner

Remove stores the character that was removed in ch. For example, where t1 is still runner.

t1.Remove(3, ch); would be removing the letter n. and the word is now runer and ch is now 'n'. It is usually desirable to use a loop.

I am using recursion because I am required to do so for this specific assignment. I know how to swap a sub string regularly, but....they want it a certain way. Thank you for putting up with this awkward framework....

L0s3r 0 Newbie Poster · Answer 3 · 2012-02-21T10:59:36+00:00

I haven't given it much thought for different cases , but it should work.

if(t2.Length() > 0)
{

if(len > 0)
{
t1.Remove(pos, ch);
t2.Remove(0, ch2);
Swap_Substring(t1,pos, len-1, t2);
t2.Add(0, ch);
t1.Add(pos, ch2);
}

if(len==0)
{
t2.Remove(0,ch);
Swap_Substring(t1,pos, len, t2);
t1.Add(pos,ch);
}

}


else if(t2.Length() == 0)
{
if(len > 0)
{
t1.Remove(pos, ch);
Swap_Substring(t1, pos, len -1, t2);
t2.Add(0, ch);
}
}

tastybrownies 0 Newbie Poster · Answer 4 · 2012-02-21T11:31:56+00:00

I really really appreciate you taking a look at this for me. It seemed like I just got carried away with if statements for my own good. The code DID work. I just did not know you could call the method more than once inside the procedure. So you can call it as many times as needed and still have your base case there at the bottom???And when you call it the instance where (len == 0) it just bypasses the case where len > 0 correct?

I also did your test case and I saw that things were correct on my up until the 5 character and then from there things went haywire. I see that my program was effectively executing the two if statements in such a fashion, where the len might not be 1 after the first call so things might not get added in continually. Is this somewhat close?

Thank you again for the big help.

Member #908245 · Answer 5 · 2012-02-21T17:28:38+00:00

Hey everyone, I am pretty new to writing procedures that deal with this idea of recursion. I am trying to get into that certain frame of mind but I am having a little bit of trouble at the last minute. My goal was to implement a text operation called swap substring using recursion.
This is what I have so far:
procedure_body Swap_Substring (
	alters Text& t1,
	preserves Integer pos,
	preserves Integer len,
	alters Text& t2
    )
{
//...
}
I'm sure some have noticed this is not straight C++. This is effectively C++ with a designated framework I have to use for university work. Any correct C++ would probably compile though. The object of this program is to swap a sub string, like so:
t1 = smile
pos = 1(where to start)
len = 2(letters to take out)
t2 = hey(to be swapped in)
See what I mean. It's like it's one letter away. This is probably some silly error, but for the life of me I can't find it after searching hours. I would GREATLY appreciate it if anyone could help me.
Thank you and have a good evening.

I was thinking,IF you have anything like a substring function or method available for your strings, OR you have access to #include <string> and it works well with this framework, it would be a VERY simple matter to just do this (requires no recursion!):

string left, middle, right, result;
//do the work
left=t1.substr(0, pos);
middle=t2;
right=t1.substr(pos + t2.size(), t1.size() - (pos + t2.size()));
//accumulate result
result=left;
result+=middle;
result+=right;

http://www.cplusplus.com/reference/string/string/substr/
http://www.cplusplus.com/reference/string/string/size/