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;
}

---

> 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.

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.

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

Quote:

---

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],

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.

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.

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]

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.

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;
}

---

Quote:

---

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;
}

---

Quote:

---

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.

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

ok nevermind my last comment. I get it now... lol it's my first programming class so thanks for the input.