Problems with understanding how recursion works in C

Question

I'm learning about functions in C from the book C Programming: A Modern Approach. It contains the following function:

int fact(int n)
{
  if (n <= 1)
    return 1;
  else
    return n * fact(n - 1);
}

with the following explanation:

To see how recursions works, let's trace the execution of the statement i = fact(3); here is what happens: "

fact(3) finds that 3 is not equal or less than 1, so it calls
   fact(2)which finds that 2 is not equal or less than 1, so it calls
      fact(1) which finds that 1 is equal or less than 1, so it returns 1,causing
   fact(2) to return  2 x 1 = 2, causing
fact(3) to return 3 x 2 = 6

I'm really confused, why does it does all these actions if it is not inside a loop? why does it keep making the 3 less and less until it matches the argument in if function?

Does the * symbol means that n in the fact(n) is now 3 - 1 and it basically says it do it all over again?

@tacocat You will really love [this](https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/trace-recursion.html) link.This is how to trace back recursion. — Ankur, Jan 04 '15 at 18:45
This link may also help you understand recursion: http://stackoverflow.com/questions/27768992/problems-with-understanding-how-functions-work-in-c#27768992 :-) — abligh, Jan 04 '15 at 19:05
See [Understanding how recursive functions work](http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — Michaël Le Barbier, Jan 04 '15 at 19:31

score 2 · Answer 1 · answered Jan 04 '15 at 19:32

Recursion is the process when a function calls itself. In the function definition you can see a call to fact(n-1), this means the function itself is called again.

int fact(int n) //return value is an integer, name of function is "fact", input argument is an integer named n
{
  if (n <= 1) // if the input arg equals 1, return 1
    return 1;
  else 
    return n * fact(n - 1); //else, return n (input arg of this fact) times the return value of fact(n - 1)
}

Fact(3) is supposed to return 3 * 2 * 1 = 6. What happens when process the statement int a = fact(3) is the following:

fact(3) //dive into this function:
{
  if (n <= 1) //n is not 1
    return 1;
  else
    return n * fact(n - 1); //now we call fact(2)
}

we call fact(2):

{
  if (n <= 1) //n is not 1
    return 1;
  else
    return n * fact(n - 1); //now we call fact(1)
}

we call fact(1):

{
  if (n <= 1) //n equals 1
    return 1; //return 1
  else
    return n * fact(n - 1); 
}

Now function fact(1) returns 1 to the point where its called, which is inside fact(2). To be precise, to the statement return 2*fact(1);, this gets passed back to the statement return 3*fact(2); which gets passed back to our initial function call and our integer 'a' gets the value 6.

I hope this made it more clear to you, if you have still questions left feel free to ask.

score 1 · Answer 2 · answered Jan 04 '15 at 19:25

Just going by your example to find the factorial of 3

The first call is fact(3)

n = 3 so else condition gets executed

3 * fact(2)

n = 2 so else condition gets executed

2 * fact(1)

n = 1 now if condition passes so it returns 1

So put together

3 * fact(2)

3 * 2 * fact(1)

3 * 2 * 1 = 6

There has to be a exit condition in recursion in this it is

if(n = 1) /* 0! = 1 So you have reached the last iteration and you are good to return */

score 0 · Answer 3 · answered Jan 04 '15 at 18:44

If you call a function from within itself it's called recursion. Since you return the value returned from the internal call, the function gets evaluated until it doesn't call itself anymore i.e. when n <= 1, < is just to account for 0! == 1.

It makes 3 or n less and less because of

fact(n - 1) // n - 1 < n

score 0 · Answer 4 · answered Jan 04 '15 at 19:16

The recursion occurs when fact(n-1) is called. There the function itself is called again, thus the code repeats itself without the need of a loop. The argument value changes because the function is called with a different argument each time.

Btw, the * symbol means a multiplication.

Problems with understanding how recursion works in C

4 Answers4

Linked