Printable View
I’m supposed to write a recursive function to count how many time does a number occur in an array. Function is in a format: count(number, array[], length);
Look at the attached txt file
I am getting an error in this line: our_sum = count(1, our_array[], 8);
error: syntax error before “]” token
What am I doing wrong???
Oh man... I need to go back to coding school. :bawling:
I might be WAY off here, but is it expecting a number between the brackets in our_array[]? It seems like you are passing our_array[] into array[9] and there is not a match there. Maybe remove the 9 from the one, or put a varible in each?
Sorry, that is my best guess. I will go home and cry into my programming books.
-Deeboe
if i define array[9] or array[] in the count function ... same error
when i pass our_array[] to a count function i know for a fact you don't have to specify elements
Wound up changing how it was done b/c I was having problems resolving the recursion in my head the way you did it, but here goes, tested it and it worked (changed array to make sure it worked in a different case). I'd probably chose to do it differently, but chose to mirror what you had as closely as I could:
In your original, pull the [9] off the function declaration and just make it [] and when you call it in the main, you don't need the []. When I use your code as is with the above change it compiles but segmenation faults (not uncommon for bugged recursion). Also personal pet peeve: int main() --> int main(int argc, int ** argv).Code:#include <stdio.h>
int count(int number, int array[], int length){
if(length < 0) { return 0; }
else
{
if(array[length-1] == number) {
return 1+ count(number, array, length-1);
}
else
{
return count(number, array, length-1);
}
}
}
int main(int argc, int **argv){
int our_sum = 0;
int our_array[] = {0, 3, 1, 2, 3, 1, 5, 1, 7, 8};
our_sum = count(3, our_array, 9);
printf("1 is in the array %d times\n", our_sum);
getchar();
return(0);
}
Anyway, like I said before, couldn't follow how y ou were using the recursion and this is probably a poor application for it, considering there are more classical uses for recursion.
Hi
I deleted my original post, since Nebulus posted the solution in the meantime.
A little correction, however :)
should be modified toCode:if(length < 0) { return 0; }
otherwise "array[length-1]" can access "array[-1]".Code:if(length == 0) { return 0; }
Another remark: "int array[]"
Nebulus has chosen this way to define the function arguments.
Another way is to use "int *array". The advantage of these two
compared with "int array[9]" is that arbitrary array-sizes are
allowed.
You actually should pass, as Nebulus did, "our_array", rather than "our_array[]".Quote:
when i pass our_array[] to a count function i know for a fact you don't have to specify elements
Or, if you wish, "&(our_array[0])" :D
Cheers.
Lol, yup your right about the length. I was screwing aroun d with several things (array subscripts, using --length, etc) and forgot to change that back. Oh well, pretty good considering I haven't seriously coded in C in ohh...hmm...7 years ? :)
EDIT: Two important concepts that weren't really mentioned with recursion:
1) Always, always, always make sure you have a terminating condition in the recursion, lest it be infinite.
-- In your code, you never checked length, you just kept calling count. So it would happily go along trying to access array[-1] array[-2], etc until it caused a core dump/segmentation fault. This is why the statement if(length <= 0) is necessary, it provides a condition for the recursion to end (and in this case returns zero since there is no array element -1, there would never be a match).
2) In this case, you want to provide a way of transferring values from recursive call to recursive call. Since you kept declaring a local variable sum, it would keep overwriting whatever you had. You can see I chose to address this with the return. So lets say you had: array= {0, 3, 2, 3} and you called sum = count(3, array, 4) and chose to print out the value of length and the value returned everytime...
It'd look like:
4, return 1+count(3, array, 3)
3, return count(3, array, 2)
2, return 1+count(3, array, 1)
1, return count(3, array, 0)
return 0
You'd then go from the bottom, upwards...so replace : 1, return count(3, array, 0) with the return from the line below, or 1, 0. Then on the next line, return 1+count(3, array, 1) would become 2, 1, and so on and so forth, until the first line looked like 4, 2, and therefore sum would be 2.
I know what you are saying about "resolving recursion in my head"
The reason i'm doing these problems is because for some reason it is very hard for me to "wrap my head around" a lot of recursion algorithms. I am just trying to find as many problems as I can find until it'll become "no-brainer" for me.
Thanx guys
... neb... system says: gotta spread AP's before giving to you
Was editing while you posted, wanted to give the thread a bump since I attempted to explain the recursion...
You are right by starting w/ the topmost element in calling the function " (3, our_array, 9)"
but the function starts counting from "array[length-1]" which mean that if the number you are looking for is in the last element you'll miss it
take out "-1"
Negative. In C, arrays are indexed 0 to length-1. for example:Quote:
Originally posted here by unhappy
You are right by starting w/ the topmost element in calling the function " (3, our_array, 9)"
but the function starts counting from "array[length-1]" which mean that if the number you are looking for is in the last element you'll miss it
how can we fix that? be right back w/ ideas
Will print:Code:int *array = {1, 2, 3, 4};
int lenth = 4;
int i=0;
for(i=0; i < (length-1); i++)
{
printf("array[%d] = %d\n", i, array[i]);
}
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
Since you are passing the length/size of the array in the call, to hit the max index of the array you have to use length-1.
run the program...
9 IS length -1
but you start CALLING the function at 9-1 which is 8
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...
#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...
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:
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 999 times!
How about them apples ;)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!
Look for yourself...what happens the first time you call it?
our_sum = count(our_number, our_array, 1000); //recursion
Ok, length is 1000, not 0, so it branches to the elseCode:if(length == 0) { return 0; }
else{
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 ;)Code:if(array[length] == number){
return 1+ count(number, array, length-1);
}
else{
return count(number, array, length-1);
}
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
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
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:
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!: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) );
}
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.
If called with 4 it prints: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) );
}
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.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