Recursion

This is a discussion on Recursion within the C++ Programming forums, part of the General Programming Boards category; I'm having a problem understanding recursion. I understand that it is like a continous loop that breaks down your big ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    Recursion

    I'm having a problem understanding recursion. I understand that it is like a continous loop that breaks down your big problem into little ones, but implementing it is a prob. I am taking an online C++ course (that probably a problem in itself) that gave a homework assignment that involves recursion.

    2.7 Implement maxarray, discussed in the section “Finding the Largest Item in an Array,” as a recursive C++ function. Note the call tree on page 84 uses a helper function named max. What does the name max imply as the purpose of the function? You will write this helper function.

    Well the figure on p84 looks pretty much like

    MaxArray(<1,6,8,3>)
    return max(maxArray(<1,6>) , maxArray(<8,3>)

    | |
    maxArray(<1,6>) maxArray(<8,3>)
    return max(<1>), maxArray(<6>) return(maxArray<8>),maxArray(<3>)
    | | | |
    maxArray(<1>) maxArray(<6>) maxArray(<8>), maxArray(<3>)
    return 1 return 6 return 8 return 3


    Any ideas ?Any help is appreciated

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    That pretty much describes exactly what you're supposed to do, doesn't it?

    What's the actual question? What are you having difficulty with?

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    When teachers ask you to write the helper function, they want you to actually write the usable function

    So what this question is asking for is to use the helper function to recursively produce the splits in the array?
    ex. Like Array[]={1,5,7,3} , how would you split this up?

    Also, in recursion, i thought u had to use the function within itself? With the code that you wrote below
    double max takes in the array and asks if the array is 2 or more? if it does then it repeats the same function again?

    like double max( maxArray[])
    {
    if (maxArray[] > 2 ) How would you do this?
    // divide array in half

    int i=0;

    if (maxArray[i] > maxArray[i+1])
    return maxArray[i]

    else

    return maxArray[i+1]


    Am I on the right track?
    Last edited by Emeighty; 07-01-2008 at 02:30 PM.

  4. #4
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    326
    Looks to me like the max function just returns the max of two values. The function that would do the recursion is maxArray. If you do have to do recursion, remember that you must have a base case. The obvious choice here is when there are no more values in the array to compare. At that point, the maximum value (that you have been keeping track of) can be returned. I guess my prototype would look something like:

    Code:
    int maxArray(int *array, int size);
    Then, for the base case, inside the function:
    Code:
    if (size == 1)
        return MAX(cur_max, array[0]);
    I'll leave the other case to you, where you actually keep track of the maximum value and compare successive elements in the array.

  5. #5
    Registered User
    Join Date
    Jul 2003
    Posts
    110
    Quote Originally Posted by MacNilly View Post
    ...The obvious choice here is when there are no more values in the array to compare....

    Then, for the base case, inside the function:
    Code:
    if (size == 1)
        return MAX(cur_max, array[0]);
    Err, I think you mean the obvious choice is when there is one element in the array:

    Code:
    if ( size == 1 ) 
        return array[0];
    since that value *has* to be the max.

  6. #6
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    Im getting the idea, but how do u split an array in half?
    Code:
      like array[]={1,2,3,4}  to  array[]={1.2} and array[]={3,4]  ?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    You could keep track of the start and end of a range, e.g., by using a pair of indices. So, with two such pairs, you would have two "halves" of the array.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

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... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 10:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21