pls help me w/ this c problem

Printable View

Show 40 post(s) from this thread on one page

January 19th, 2006, 06:44 PM
unhappy

run the program...

9 IS length -1

but you start CALLING the function at 9-1 which is 8
January 19th, 2006, 07:33 PM
nebulus200

Bleh so I miscounted, sue me :)

It'd be better off to do something along the lines anyway (for this very reason):

int length = sizeof(our_array) / sizeof(our_array[0]);

That's what I get with screwing with it at the last minute before I posted it. Regardless, the logic of the function is still correct and length-1 should still be used. The function should just be called correctly by passing the correct length of the array. And while we are at it, I'll go ahead and point something else out, the output is wrong b/c I never updated the '1' to be '3', but the idea was to illustrate and attempt to explain recursion, not necessarily to provide a flawless program.

Regardless, this kind of thing is a bad application of recursion since its much easier to approach it with a straight forward search through the array (especially from an overhead standpoint, since when you use recursion, you essentially keep throwing more and more stuff on the stack everytime you call it).

A good example of recursion would be the implementation of the greedy algorithm for providing a minimal amount of coins for change given a certain decimal amount (for example, 85 cents: 3 quarters and a dime). Where the function would take the biggest chunk out first (that is what makes it greedy), then call itself again with how much is left to go...

Something like that might make it a little easier to follow and understand since the logical way of deriving change is by nature recursive...
January 19th, 2006, 08:30 PM
unhappy

#include <stdio.h>

int count(int number, int array[], int length){ //nebulous' sexy recursion algorithm
if(length == 0) { return 0; }
else{
if(array[length] == number){
return 1+ count(number, array, length-1);
}
else{
return count(number, array, length-1);
}
}
}

int main(){

char line[100]; //line of input
int i, our_number = 0, our_sum = 0, our_array[1000]; //index, input, count, array

for (i = 0; i < 1000; i++){ //polulate the array w/ random numbers and print
our_array[i] = rand();
printf("%d, ", our_array[i]);
}

printf("Enter the number you want to look for: "); //input routine
fgets (line, sizeof(line), stdin);
sscanf (line, "%d", &our_number);

our_sum = count(our_number, our_array, 1000); //recursion
printf("\nNumber %d is in the random array %d times! \n", our_number, our_sum); //output

getchar();
return(0);
}

when you have time can you pls make it so i can put in command line args...
January 19th, 2006, 08:54 PM
nebulus200

Alright, so I see you dropped the -1 from the check...

Now to test, the only change I made in your code was instead of using rand() to seed the array, I set every value to 0 (to test the extreme case of they all match), and you get:

Quote:

./a.out
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, Enter the number you want to look for: 0

Number 0 is in the random array 999 times!

Oops, missed one. I then went in and changed the check in count to use array[length-1] (as I originally posted), recompiled and ran again:

Quote:

./a.out
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, Enter the number you want to look for: 0

Number 0 is in the random array 1000 times!

How about them apples ;)

Look for yourself...what happens the first time you call it?

our_sum = count(our_number, our_array, 1000); //recursion

Code:

if(length == 0) { return 0; } else{

Ok, length is 1000, not 0, so it branches to the else

Code:

if(array[length] == number){ return 1+ count(number, array, length-1); } else{ return count(number, array, length-1); }

Since length is 1000, you check array[1000] which is in reality undefined, its outside of the scope of the array. Either way, if it doesn't core dump for going outside of the array, it'll branch to the else and call itself with 999, which would still work...the problem is that when I wrote the original function, I used length-1, so the proper termination of the recursion is when length=0; however, when you changed it to just [length] it no longer takes into account array[0] is a valid index, so the first element is never checked, the recursion returns 0 because length is zero. If you insist on doing it the way you are doing it and don't mind accessing outside the bounds of the array on the first pass, you could change the termination check to if (length < 0), then all is well b/c it will still call when length is zero, still check array[0] and the proper count will return, count will get called again with length=-1, which < 0, which returns 0. Or you could just use it like I had it and it works out of the box ;)
January 19th, 2006, 11:14 PM
unhappy

I don't get it ... I understand the mistake of array[1000] not existing... OK I got that ...

but after that the recurstion should procede exactly the same as array[999] and counting as in your example

why does it skip array[0]???

quote "can't wrap my head around this"

f-ing recursion
January 19th, 2006, 11:22 PM
unhappy

another thing i don't get is this:

if(array[length-1] == number){
return 1+ count(number, array, length-1);

let's say that array[length-1] = array[3] is the number we are looking for so we return +1

but the count method in return statement should be still "array[length-1] = array[3]" and that's how it will go forever and forever...

i don't get where do we actually subtract the length ... it seems it should stay constant no matter how deep you go into the recursion
January 20th, 2006, 12:25 AM
nebulus200

Ok, I think you are missing something pretty important along the line, so I am going to back up and drop to a very simple example.

Calculate the factorial of n (n!) = n * (n-1)!, n>1:
so
5! = 5*(4!) = 5*4*(3!) = 5*4*3*(2!) = 5*4*3*2*1
4! = 4*(3!) = 4*3*2! = 4*3*2*1
7! = 7*6! = 7*6*5! = 7*6*5*4! = 7*6*5*4*3! = 7*6*5*4*3*2! = 7*6*5*4*3*2*1

So your function is going to be along the lines of:

Code:

int factorial(int x) { if(x <= 1) { return x; } else { return x * factorial(x-1); } } int main(int argc, char **argv) { char line[100]; int n; printf("Enter the number to compute the factorail (keep it < 10): "); //input routine fgets (line, sizeof(line), stdin); sscanf (line, "%d", &n); printf("%d! is %d\n", n, factorial(n) ); }

The important thing to realize here is that in the return statement: return x * factorial(n-1) is that to compute the return value, it must call factorial again. So lets say that you enter '4' to compute 4!:

printf will call factorial(4)
since 4 > 1, factorial(4) will return 4 * factorial(3) (which will call factorial with 3 (n=4, so n-1 = 3)) (4 > 1 is the negation of x <= 1)
since 3 > 1, factorial(3) will return 3 * factorial(2) (which will call factorial with 2)
since 2 > 1, factorial(2) will return 2 * factorial(1) (which will call factorial with 1)
since 1 <= 1, factorial(1) will return x or 1.
factorial(1) then returns a value of 1 to factorial(2)
factorial(2) may then return a value of 2 (2 * factorial(1) ) to factorial(3)
factorial(3) may then return a value of 6 (3 * factorial(2) ) to factorial(4)
factorial(4) may finally return the value of 24 (4 * factorial(3) )

So as in the mathematical example, factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4*3*2*1

To see this in action add print statements.

Code:

int factorial(int x) { int value; printf("Beginning factorial with x = %d\n", x); if(x <= 1) { value = x; } else { value = x * factorial(x-1); } printf("factorial called with x = %d and returning %d\n", x, value); return value; } int main(int argc, char **argv) { char line[100]; int n; printf("Enter the number to compute the factorail (keep it < 10): "); //input routine fgets (line, sizeof(line), stdin); sscanf (line, "%d", &n); printf("%d! is %d\n", n, factorial(n) ); }

If called with 4 it prints:

Quote:

Enter the number to compute the factorail (keep it < 10): 4
Beginning factorial with x = 4
Beginning factorial with x = 3
Beginning factorial with x = 2
Beginning factorial with x = 1
factorial called with x = 1 and returning 1
factorial called with x = 2 and returning 2
factorial called with x = 3 and returning 6
factorial called with x = 4 and returning 24
4! is 24

You can see from the order of the output, that the factorial function with 4 calls it with 3 calls it with 2 calls it with BEFORE any output from the end of any of the functions is out there...Then you can see in reverse order the functions finishing. The reason for this was explained above.

Show 40 post(s) from this thread on one page