Recursion in C

Omid

Look at this code :
27: unsigned int factorial(unsigned int a)
28: {
29: if (a == 1)
30: return 1;
31: else
32: {
33: a *= factorial(a-1);
34: return a;
35: }
36: }

The code evaluates fcatorial of "a". The only point I don't get is the return in line 30. When the function is called, each time "a" is increased by 1, so it will reach 1 finally. If so the function must always return 1 and not a. Because always reach 1.
Thanks

faust9

Talk it through...

let a=4
4 != 1 so the if portion is skipped for now.

4*=factorial(3)

3 != 1

3*=factoral(2)

2 != 1

2*=factoral(1)

1==1 so 1 is returned

2*1=2 so 2 is returned

2*3=6 so 6 is returned

6*4=24 so 24 is returned

The function doesn't get to the 'return a' until the factoral(a-1) returns a number which doesn't happen until a==1.

Recursive functions should be avoided at all costs because they get very unweildy very quickly. Large numbers would consume a lot of memory to do something as simple as a factorial.

Omid

Now when I see the code, find that I missed an important point :
Even if a function returns 1000 different values the only accepted one is the first.
So the 1 returned each time is simply ignored because that's the second returned value by factorial function.

Thanks, anyway

faust9

I don't know what you mean by this. In C, a function can only return one value (you can get around this using structures/unions and more importantly pointers). I don't know if you understand what is really happening here or not. The program doesn't get to the 'return a' command until the factoral function is done. The factoral function doesn't get done until the program decrements a down to 1. Once a is decremented to 1 then and only then does the factoral function begin returning values. Is this what you meant? It's an important concept in that a line of a program isn't executed until the previous line is completly done.

Omid

I don't really understand the code, that's why I sent this post.
When a==1, the If statement is executed and function returns 1. When does it send a ? When a==1 the If part is executed not the else part.

I thought each time the function returns two values, "a" and 1 because 1 is the second it is ignored. I tested this idea and it worked well. I defined a function called test :
int test() {
return 1;
return 2;
return 3;
}
When I ran the code it only returned 1, the first return.
Please consider that I've just started to learn C.

faust9

Your function (I removed the unsigned type)
A simple program to use the above.
Please forgive me if you already know this; however, I don't want to jump to any conclusions about your level of understanding.

A computer reads a program one line at a time only. A computer executes each line as it reads it. A computer has no knowledge of what the next line says, only where to find the next line in memory. Disregard pipelining for this discussion. If you keep this in mind it should help you understand what a piece of code is doing. While you can clearly see the 'return a' and know what it is supposed to do the computer cannot. The computer does not know there is a 'return a' immediatly after the 'a*=factoral(a-1)' line. Whith that in mind lets talk through the simple program above and see what is happening.

ignore the stdio.h. The computer never see this. The compiler uses this to replace the printf() function with code that the computer can understand.

1-int main()

this is the opening function call. main encapsulates the program which is going to be executed.

2-int a=6;

I use this to make it easy to change the value of a. Try not to use real numbers in functions. Use variables instead because you can locate all of your variable assignments in a central location making it easy to change your code without having to look for all of the appropriate constants to modify.

3-int fact=factoral(a)

creates an integer called fact which is equat to the factoral of 6

Here's where the program jumps to the factoral function. Remember, we can see the printf function but the computer can not. The 'int fact=factoral(a)' call is telling the computer to create a new factoral function and give that function the value of 6 to work with. The computer jumps to the factoral function.

4-The first factoral function where factorial(6) is used.

5-The computer asks "Is it true that a == 1" by using an if(a==1) statement.

in this case no. a==6 which is not equat to 1 so the answer is false. the computer moves to the else statement

6-The computer says "I have to multiply a by the result of factoral(5) and put that answer back into a when I'm done" a *= factorial(a-1).

The computer cannot multiply a by anything yet because factoral it does not know what factoral equals. Factoral has not returned a value yet so this part of the program must wait for factoral to return a value in order to procede.

Again, the computer has no idea there is a return a statement directly below the a*=factoral(a-1) statement. The only thing the computer knows is that is has to generate a newfactoral function where factoral(5) is used.

7-The first factoral function where factorial(5) is used.

8-The computer asks "Is it true that a == 1" by using an if(a==1) statement.

in this case no. a==5 which is not equat to 1 so the answer is false. the computer moves to the else statement

9-The computer says "I have to multiply a by the result of factoral(4) and put that answer back into a when I'm done" a *= factorial(a-1).

The computer cannot multiply a by anything yet because factoral it does not know what factoral equals. Factoral has not returned a value yet so this part of the program must wait for factoral to return a value in order to procede.

Again, the computer has no idea there is a return a statement directly below the a*=factoral(a-1) statement. The only thing the computer knows is that is has to generate a newfactoral function where factoral(4) is used.

10-The first factoral function where factorial(4) is used.

11-The computer asks "Is it true that a == 1" by using an if(a==1) statement.

in this case no. a==4 which is not equat to 1 so the answer is false. the computer moves to the else statement

12-The computer says "I have to multiply a by the result of factoral(3) and put that answer back into a when I'm done" a *= factorial(a-1).

The computer cannot multiply a by anything yet because factoral it does not know what factoral equals. Factoral has not returned a value yet so this part of the program must wait for factoral to return a value in order to procede.

Again, the computer has no idea there is a return a statement directly below the a*=factoral(a-1) statement. The only thing the computer knows is that is has to generate a newfactoral function where factoral(3) is used.

13-The first factoral function where factorial(3) is used.

14-The computer asks "Is it true that a == 1" by using an if(a==1) statement.

in this case no. a==3 which is not equat to 1 so the answer is false. the computer moves to the else statement

15-The computer says "I have to multiply a by the result of factoral(2) and put that answer back into a when I'm done" a *= factorial(a-1).

The computer cannot multiply a by anything yet because factoral it does not know what factoral equals. Factoral has not returned a value yet so this part of the program must wait for factoral to return a value in order to procede.

Again, the computer has no idea there is a return a statement directly below the a*=factoral(a-1) statement. The only thing the computer knows is that is has to generate a newfactoral function where factoral(2) is used.

16-The first factoral function where factorial(2) is used.

17-The computer asks "Is it true that a == 1" by using an if(a==1) statement.

in this case no. a==2 which is not equat to 1 so the answer is false. the computer moves to the else statement

18-The computer says "I have to multiply a by the result of factoral(1) and put that answer back into a when I'm done" a *= factorial(a-1).

The computer cannot multiply a by anything yet because factoral it does not know what factoral equals. Factoral has not returned a value yet so this part of the program must wait for factoral to return a value in order to procede.

Again, the computer has no idea there is a return a statement directly below the a*=factoral(a-1) statement. The only thing the computer knows is that is has to generate a newfactoral function where factoral(1) is used.

19-The first factoral function where factorial(1) is used.

20-The computer asks "Is it true that a == 1" by using an if(a==1) statement.

in this case yes. a==1 so the computer proceeds through the if statement finally.

21-The computer finally returns a value to a calling function. return 1 sends the value one back to the function that called it. Remember each iteration of the recursive function generated a new function so the value of 1 is returned to the function factoral(2).

22-a*=factoral(2) finally has a value to work with.

lets rewrite a*=factoral(1) so it is more readable.

a = a * factoral(1).

remember we are now working in factoral(2) so a==2. The computer does the following:

a = 2 * 1

a=2

23-Now the computer proceeds to the next step of the program---the 'return a' statement. the factoral(2) function returns a value of 2 to the factoral(3) function.

24-a*=factoral(3) finally has a value to work with.

a = a * factoral(2).

remember we are now working in factoral(3) so a==3. The computer does the following:

a = 3 * 2

a=6

25-Now the computer proceeds to the next step of the program---the 'return a' statement. the factoral(3) function returns a value of 6 to the factoral(4) function.

26-a*=factoral(4) finally has a value to work with.

a = a * factoral(3).

remember we are now working in factoral(4) so a==4. The computer does the following:

a = 4 * 6

a=24

27-Now the computer proceeds to the next step of the program---the 'return a' statement. the factoral(4) function returns a value of 24 to the factoral(5) function.

28-a*=factoral(5) finally has a value to work with.

a = a * factoral(4).

remember we are now working in factoral(5) so a==5. The computer does the following:

a = 5 * 24

a=120

29-Now the computer proceeds to the next step of the program---the 'return a' statement. the factoral(5) function returns a value of 120 to the factoral(6) function.

30-a*=factoral(6) finally has a value to work with.

a = a * factoral(5).

remember we are now working in factoral(6) so a==6. The computer does the following:

a = 6 * 120

a=720

31-Now the computer proceeds to the next step of the program---the 'return a' statement. the factoral(6) function returns a value of 720 which is assigned to fact. Fact can now be used in the printf() function to display the results.

32-printf("The factorial of %d is: %d", a,fact) displays the following:

The factoral of 6 is: 720

33-return 0 tells the operating system that the program is done executing and can be closed.

faust9

Sorry the above was so long, but that's one of the bad things about recursive functions. They consume a lot of memory when easire methods ususally exist. You have to keep in mind that when a function is called a new function is created using the function code as a framework. Each new function call must wait for the next function call to return a value before continuing on and returning a value to the previous function call.

Again, I know this is long but I've tried to lay it out as the computer would execute it step-by-step. This is how you read a program (until you get the feel for things like this). You read it step by step. You don't look to the next step until the previous step is complete. It's long and drawn out but that's how you do it.

Good luck, and hope this helped clear things up. I don't know how to put this any other way except step-by-step. Recursive functions are difficult at first but once you see what is happening they become exceedingly easy.

Anteros

I think the misunderstanding might just be in the if/else syntax.

is equivalent to...

so there is only one return statement in each possible code branch. If the if statement is false, the "return 1;" code is never executed, it branches into the else block.

The key concept is that if you don't put the curlies after an if statement the contents of the block is assumed to be a single line following the statement.

The function only hits one return statement per invocation.

Omid

faust9, Anteros thank you very much.
Your explanations cleared it up. Now by your explanations I think I understand recursion very well.
Thanks again

sick

ummm another help in recursion...pllssss
faust i need your explanation....
---------------------------------------------------
#include <stdio.h>
void up_and_down(int);
int main(void)
{
up_and_down(1);
return 0;
}
void up_and_down(int n)
{
printf("Level %d: n location %p\n", n, &n);
if (n < 4)
up_and_down(n+1);
printf("LEVEL %d: n location %p\n", n, &n);
}
Level 1: n location 0022FF60
Level 2: n location 0022FF40
Level 3: n location 0022FF20
Level 4: n location 0022FF00
LEVEL 4: n location 0022FF00
LEVEL 3: n location 0022FF20
LEVEL 2: n location 0022FF40
LEVEL 1: n location 0022FF60
-------------------------------------------------------
that is the code...
i don't know why that it prints LEVEL 3 because...
in my own understanding...
when
if (n < 4)
up_and_down(n+1);
was false...i understand why LEVEL 4 appeared but then why is it LEVEL 3 appeared?
cause it would return to up_and_down(3); << and this line would go again in
the function and maybe would add 1 again so that it would became 4...
help me... plss.

rcgldr

What wasn't mentioned before is local variables, including paramters for a function are kept on a stack. Think of a stack as a very long array. The convention for a stack is to start at the last location for the array, and then to store values using decreasing indexes. What your function is doing here is displaying the addresses in the stack where all the "instances" of "n" are being stored.

Note that there is only one copy of the function in memory. Each time you call a function, things like the return address and paramters are added to the stack, in decreasing index order. This is true even if a function calls "itself".

In this particular case, the first time up_and_down is called, an "instance" of n is placed on the stack at index 0x0022FF60. When up_and_down calls itself, yet another instance of "n" is placed on the stack at index 0x0022FF40. There is also some overhead such as a return address in functions, which is why each instance of "n" is 32 bytes apart on the stack.

When up_and_down calls itself for the fourth time, that instance of "n" ends up at 0x0022FF00, and at this point there are four instances of "n". ALthough the name is the same, there are really 4 "n"'s at this point. Then when the forth call to up_and_down returns back to the 3rd call, it shows the 3rd instance of "n" is still at the same spot. Then the 3rd call returns to the second call, and then to the first, which returns back to main. Each one showing that the address of the 4 "n"'s were the same when calling or returning.

sick

thanks jeff ummm another question...
umm when the program skips the execution in up_and_down(n+1);
i know why the LEVEL 4 is output...so it return to the 3 value....
the next line is this up_and_down(3); am i right? so it calls again the up_and_down();
function...my question is when up_and_down(3); is called why it skips the if statement
that make an output in LEVEL 3..2..and so on.. thanks
umm another question about the stack...
how many bytes that the stack can only hold? thanks

arifkingkhan

Actually recursively calling to function end when n=4.Because then if condition is false & below statement connected with if doesn't execute.But a function terminate when it get a return value & if void function then it terminate when end of statement is reached so below printing statement is execute and it prints 4.as at that time n=4.and last funtion terminates..
but the revious one function waits for this function to terminate .As soon as this terminates with printing 4.function before it do the execution of the statement below the terminated one funtion.as the prev func waits at that point.Not at begining.......

you'r ques is why it skips the if statement
that make an output in LEVEL 3..2..and so on..

because as soon as last function terminate printing 4.Execution is done of statement below that function.as again no funtion is calling again.only termination of each is done by executing the left portion of program inside in each func.which it does'nt execute