Thread: C minimum recursive function help

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    4

    Unhappy C minimum recursive function help

    I don't understand how this function works exactly. I would appreciate it if someone could thoroughly walk through the code that would be great. It basically finds the minimum value in an array. I specifically don't understand the min = part and some of the code after that
    Thanks in advance.

    insert
    Code:
    int minimum(const int[a], int count){
      int min;
    
      if(count <= 0 )
        return 0;
    
      min = minimum(a, count - 1);
    
      if (count == 1 || a[count - 1] < min)
        return a[count - 1];
    
      return min;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > min = minimum(a, count - 1);
    This is the min of the first count-1 elements

    > a[count - 1] < min
    This compares the min of all other elements with the last element
    Return whichever is smaller.

    Try it with an array with 2 or 3 elements in it, then step through it with the debugger.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    will this even compile
    int minimum(const int[a], int count)

    don't think I've seen a declaration like that before

    edit:: and its probably not the best recusion example to look at. Very inefficient for just finding minumum number. google fibinocci recusion, if your trying to learn how recusion works, those are better examples I would think.
    Last edited by sl4nted; 12-10-2006 at 02:01 PM.

  4. #4
    Registered User
    Join Date
    Dec 2006
    Posts
    4
    insert
    Code:
      a[5] = {10,7,3,11,4};
    count = 5

    I still don't see what min is assigned to.
    the first time around it seems that it is minimum(a,4),
    but that is not a value b/c we haven't calculated it.
    Couldn't it just be any value in the array?

    so how can we then compare a[4] < min?

    sorry if that is confusing

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    the first time around it seems that it is minimum(a,4),
    but that is not a value b/c we haven't calculated it.
    exactly, thats recusion....min is not actually set untill the first return...which is when count = 0

    so what it does is this:

    Code:
      if(count <= 0 )
        return 0;
    
      min = minimum(a, count - 1);
    all that does is recur once for every element in the array
    the return 0 is maybe confusing...but really its just an arbitrary number...it would still work if it was 999999 or -8888 etc.
    since once count = 1; it just returns a[0] anyways, then function calls start to unwind, and whatever was smallest out of the previous positions in the array is tested against [count - 1],
    Last edited by sl4nted; 12-10-2006 at 03:05 PM.

  6. #6
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    If sl4nted is being confusing, I prefer to say that you only compare count - 1 elements, see?
    if (count == 1 || a[count - 1] < min)
    So the correct way to call this function is
    minimum(a, sizeof(a) / sizeof(*a));
    like people've been doing.

    This code:
    if ( count <= 0 ) return 0;
    min = minimum(a, count - 1);

    fills the call stack. If you haven't gone through it with a debugger, do so. It can be enlightening.

    I also don't see why you think it's such a bad function sl4nted. Apart from overflowing the stack in the case of the big array, this certainly can show someone what recursion is. There are faster ways to do this particular thing, of course.
    Last edited by whiteflags; 12-10-2006 at 03:16 PM.

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    I don't think its a good example becuase like we've stated, for the problem, it is uneeded, and inefficient. I would never use this to find the minimum in an array, so why study it? If you want to learn a method of doing somthing, look at an example specific to that method. Recursion is only used for certain instances and problems, so looking at an example that benefits from recusion will let you see better why it works.

  8. #8
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    I agree with sl4nted in that this is probably more of a textbook function than a useful example of recursion. Anyways, if you are still having trouble understanding recursion, you can just think of it as creating many "unfinished" instances of the same function. Each instance is unfinished, because it relies on the return value of yet another call to itself. Without this return value, the function "instance" cannot continue and will not end. At some point however, based on some condition, the function will stop calling itself. The condition here is count <= 0. Once this happens, the number of function "instances" will start to decrease, as the instances can now finish, however this occurs in reverse order of creation.

    Here's an example for this function, if you call it with count = 2
    1st Instance
    1) count is 2, so not <= 0, so the function does not return 0
    2) min is set to the return value of the function with count = 1
    Therefore "instance 2" is created, and "instance 1" just waits now

    2nd Instance
    1) count = 1, not <= 0
    2) to set min, a third instance is needed (with count = 0). Now both Instance 1 and 2 wait...

    3rd Instance
    1) count <= 0
    2) This instance returns 0 and therefore the function call is completly finished. Now the 2nd instance will have min set

    2nd Instance
    1) min is now 0. The function can continue
    2) Instance 2 returns a[count - 1] = a[0] and finishes (since count == 1)

    1st Instance
    1) min is now a[0] (and count is 2 here still)
    2) If a[count -1] (( == a[1] )) < min == (( a[0] ))
    Returns a[1]
    3) Else Returns a[0]

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    I throw that text book right in the garbage. Right after I went to the appendix and cut out the
    how to impliment your own sum function using recursion example:
    Code:
    int myadd(int a, int b)
    {
            int i;
    
            if (b > 0) i = myadd(a, b - 1);
    
            return a + b;
    }
    and stuck it on my fridge.

    j/k, but you have to learn when and why to use it, not just how. and examples that show all these are just better.
    Last edited by sl4nted; 12-10-2006 at 11:29 PM.

  10. #10
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    I like your addition function. Now just need one for multiplication.
    Code:
    int fast_multiply(int a, int b) {
    if(b > 0)
      return(myadd(a, fast_multiply(a, b - 1)));
    return 0;
    }

  11. #11
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    I like your addition function
    this function has nothing to do with recursion, because the i is not used
    so after compilers optimisation it is equivalent to
    Code:
    int myadd(int a, int b)
    {
            return a + b;
    }
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  12. #12
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    this function has nothing to do with recursion, because the i is not used
    I think that was the whole point. It was an example of where you just shouldn't use recursion.

  13. #13
    Registered User
    Join Date
    Dec 2006
    Posts
    4
    Ok, thanks for the help... but,
    It is still not clear to me that the function will ever return 0.
    It seems that is should stop calling itself after is gets to count == 1.
    Thanks for the step by step coder8137

  14. #14
    Registered User
    Join Date
    Dec 2006
    Posts
    4
    ok nevermind my last comment. I get it now... lol it's my first programming class so thanks for the input.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  2. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  3. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  4. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM