Is this an okay recursion function...

[Minime80]

Okay, I had to write this function that was recursive and added all the even numbers in an array. Here's what I came up with.
int add_evens(int *ary, int &len, int j, int tmp)
{
if( j < len )
{
if( ary[j] % 2 == 0 )
{
tmp += ary[j];
add_evens(ary, len, j+1, tmp);
}
else
{
add_evens(ary, len, j+1, tmp);
}
}
else
{
return tmp;
}
}
I think it's pretty self explanatory, and it does what it should, but I'm the type of person that always wants to learn how to do it better so if you see a way to make it more efficient, less code, or see something that's redundant please feel free to teach me. Thanks.

[TacKat]

Unless this has to be recursive for a particular reason, it'd be better in a loop. However, assuming that it does you can still fix it up a little. You don't really need either of the 'else' statements in there. Pull the add_evens call out of your modulo if block, because either way (the number is even or odd) you call that function with the same arguments.

The second 'else' isn't really needed because the function is trapped in the 'j < len' if block until it's covered all the array elements. It's not going to break out of that if until it's done with everything so you don't need to have an else "protecting" the return.

Additionally, a simpler way (in my mind) to determine if a number is even is to use a bitwise AND (&). AND your value with 1, if the result is 0 then it's an even number. This is because the only way a binary number can be odd is if the first bit is set; you don't need to go dividing anything out.

[Minime80]

Actually the else on the return is necessary because when the function finally gets to the return it backs out of recursion iteration by iteration and starts right after the function call and will return each consecutive value of tmp if the return tmp isn't protected, and you'll end up with either a 0 value (if the first element was odd) or just the value of the first element (if it was even)

[The Kooman]

Originally posted by Minime80:
<STRONG>Okay, I had to write this function that was recursive and added all the even numbers in an array. Here's what I came up with.
int add_evens(int *ary, int &len, int j, int tmp)
{
if( j &lt; len )
{
if( ary[j] % 2 == 0 )
{
tmp += ary[j];
add_evens(ary, len, j+1, tmp);
}
else
{
add_evens(ary, len, j+1, tmp);
}
}
else
{
return tmp;
}
}
I think it's pretty self explanatory, and it does what it should, but I'm the type of person that always wants to learn how to do it better so if you see a way to make it more efficient, less code, or see something that's redundant please feel free to teach me. Thanks.</STRONG>

I think it's pretty self explanatory, and it does what it should, but I'm the type of person that always wants to learn how to do it better so if you see a way to make it more efficient, less code, or see something that's redundant please feel free to teach me. Thanks.[/QB][/QUOTE]


How about this ;):

int add_evens(int *ary, int &len, int j, int tmp)
{
return (j &lt; len) ?
(((ary[j] % 2) == 0) ?
add_evens(ary, len, j+1, tmp+ary[j]) :
add_evens(ary, len, j+1, tmp)) :
tmp;
}


Hmmm, ... doesn't that look like LISP now :D?

[pinoy]

int add_evens(const int *array, size_t len)
{
const int *end = array + len;
int result = 0;
for (; array &lt; end; array++)
result += (*array % 2) ? 0 : *array;
return result;
}

[Minime80]

Alright. That last one wasn't even a recursive function. It at least has to be a recursive function.

[pinoy]

Yes, because your example is *NOT* an okay recursive function.

[jemfinch]

Originally posted by pinoy:
Yes, because your example is *NOT* an okay recursive function.

Maybe not in C, but every function is an okay recursive function. It's archaic compilers that ignore the advances made in computing for the past 30 years that lead recursive functions such as his to be inefficient.

Jeremy

[Niminator]

Keep in mind this a simply a learning exercise, and writing this as a recursive function isn't considered efficient. Also remember that each recursion pushes all of your parameters onto the stack. Yours was passing the array address, a running total, the current place in the array, and the total numbers in the array. that means each time you called the function, you consumed 4 'slots' in the stack. The example below accomplishes the counting with only 2 slots.



int add_evens(int array[], int n)
{
n--;
if(n==0) return array[0];
if(array[n]%2=0
return (array[n]+addevens(array,n);
return(addevens(array,n);
}


I like it this way for several reasons, first that your function interface is prettier. All you have to pass is the array and the array size. It's cleaner, easier to remember, and most importantly, universally understood; This how almost everyone passes arrays. Second, this one only consumes 2 slots on each recursive call, half as much.

there are 2 basic rules to recursion.
1. there must be special cases to handle the simplest computations, in this example when the array is on its last number.
2. each recursive call must simplify the problem. In this example, I simplify by decrementing the number of items in the array each time.


By the way, consuming 2 or 4 whole slots (actually memory addresses, so 4 bytes per address) isn't too big of a deal since you have 2 gigs of space to play in, but you get the picture.

Another thing you could do is set a const variable inside the function to keep a running total. That way you don't have to pass it.

[ 01 October 2001: Message edited by: Niminator ]

[pinoy]

Originally posted by jemfinch:
<STRONG>Maybe not in C, but every function is an okay recursive function. It's archaic compilers that ignore the advances made in computing for the past 30 years that lead recursive functions such as his to be inefficient.

Jeremy</STRONG>

Yes, you've been through this over and over before. The example is written in C (well C++ actually), which does not handle recursion well. I'm not sure about your Ocaml, but the fact is *MOST* recursive calls will involve some sort of stack (whether it is optimized into a loop or not) for storing state information. In this case the recursion can be optimized into a loop without any stack requirement.

C/C++ isn't archaic, I still use it to build commercial products. Just because you don't understand it fully enough, does not make a language bad. I know you know C/C++, but it's different to really know C/C++. And beside it's nothing to do with compilers, it's mostly to do with the paradigm you use. There are lots of paradigms out there, imperative, functional, object oriented, generic, ... Now if you use imperative programming in Ocaml, you'd probably be screwed, it may work (then again it may not, I don't really know Ocaml) but the point is, that's not the effective way of using Ocaml. It's the same with C++, if you program C++ like C, you are basically writing C programs just using C++ extensions, and you're not using the language to its fullest.

Now I believe Ocaml doesn't support generic programming because it's got no way of passing types (like C++ has). Should I say that Ocaml is an archaic language? I don't understand functional programming much myself, but if you do use functional programming, you'd have to change your perspective. Which is probably where you're looking at, and I can only assume that these kind of techniques are common in that paradigm.

Now back to the original example, which was written in C++ (in this case he used an imperative programming paradigm, no OO here), would you say that in this paradigm, this is a good recursion example?

[kmj]

pinoy, I think you're missing the point. Most likely, Minime has to use recursion. This is probably an assignment, probably to get familiar with recursion. It doesn't matter whether or not there may be a better way.

[pinoy]

kmj:
Yes, I may missing the point, but the question is "Is this an okay recursive function?" I say no, and it should be written as a loop instead.

[tnordloh]

I like the Towers of Hanoi. An exercise where recursion actually simplifies the code.