Thread: recursion problem

  1. #1
    Registered User
    Join Date
    Nov 2001

    recursion problem

    Objective: write a completely inneficient recursion function that will copy two arrays and one that will compare two arrays.

    I'm given an algorithm I have to use, hell the prof even told us what the first call should look like. The array data is read in from some file, it's all ints. Say my first array has 7 values before I reach an (we'll call it) array input termination character, sounds fancy enough, in the input file. I write a null as the next item in the array, unless the last item brought the num. of items to the max, which in this case is 50. Now here's the algorithm for copying that array into some other array (paraphrased): Your copy function should recursively copy half the range of the range given from the original array into the new array. An example of the first call for an array that contains 7 values would read something like this, copy(x, y, 0, 6).

    Here's the rub, if you send the first and last indexes for what you want to copy, and you continue to divide in half you'll either come up with a continuous loop or you'll lose either the first or last index in the copy, depending on your stop case (the case where the function returns, doing nothing else first).

    Here is what I have so far, to show you what I mean above about not being able to obtain the copy of the first or last values, as well as another idea that ends up with an infinite loop. Btw, I've been programming for much longer than I've been taking this b.s. course, so don't use kid gloves in answering this post please. ty

    Idea 1:
    void copy (int old[], int new[], int start, int end) {

    if(start+1 == end)
    new[start] = old[start]; // This way I'll never be able to copy the last
    // member of old into new. If I did
    // new[end] = start[end] I would be able to,
    // but then I would never copy the first member

    else {
    copy(old, new, start, start+(end/2));
    copy(old, new, start+(end/2), start);
    I do realize that in Idea 1, if I send the first index to copy and one more than the last index to copy it will work as I want it to (ie. for an array with 7 items in it, I would do copy(x, y, 0, 7) and that would copy 0 - 6), but the class being as F#!@^*$ annoying as it is, the T.A. says, "No, don't do that." So I tried something else, but this doesn't work at all. I'm just throwing it out to stir ideas.

    Idea 2:
    It's exactly the same except instead of start+1 == end in the if statement, use start == end. It doesn't work, the second copy call is continuous.

    Once I have the copy or compare function the other is easy, they use the same algorithm. Any help would be greatly appreciated. Thanks in advance


  2. #2
    Registered User NewtonApple's Avatar
    Join Date
    Aug 2001
    I'm assuming both arrays are the same size.. so here is what I think:
    void copy (int Old[], int New[], int start, int end)
         if ( start == end )
             Old[start] = New[end];
             copy(Old, New, start, start+(end-start)/2); 
             copy(Old, New, start + (end-start)/2+1, end); 
    something needed to be pointed out. I think your original probably won't give you all ranges from the arrays... to see why, just plug in 10 for 'start' and 14 for 'end' and you'll see what I mean.. your array will actually go out of bound that way.. I think the above code will work.. at the moment I don't have anything I can compile the code with.. so if there's any bugs, sorrie in advance...
    Last edited by NewtonApple; 11-11-2001 at 03:16 PM.
    Everyone sucks... because of gravity...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion problem
    By trnd in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 03:06 PM
  3. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 03:52 PM
  4. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM
  5. recursion problem
    By dustinc in forum C++ Programming
    Replies: 1
    Last Post: 10-29-2001, 04:29 AM