recursion problem

Hello, I am currently learning about recursion, and I am having serious problems understanding this piece of code from my book. I believe I am understanding the first few steps to the recursion but after that I am failing to understand where the numbers are coming from, if anyone could please explain this to me, I would greatly appreciate it.

I have pasted the code below, where I am having the problem is, say I put 3 in as the factorial. I understand until the if (n==1) return , line is executed. But after than I do not understand. For instance, n is now 1 at this point, but when the line answer = factr(n - 1) next executes, n is 2, and then when it executes again next time around n = 3, when i expected it to be 1 since (2 - 1). Why is n suddenly increasing?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  #include <iostream>

using namespace std;

int factr(int n);

int main()
{
	int factorial;
	cout << "Enter number for factorial \n";
	cin >> factorial;
	cout << "Factorial of : " << factorial << " is " << factr(factorial);

 	return 0;
}

int factr(int n)
{
	int answer;

	if (n == 1) return (1);
	answer = factr(n - 1) * n;
	cout << answer << "\n";
	return(answer);
}
Last edited on
You call factr(3).

The 3 is not 1, so answer = factr(2) * 3;

There is a call of factr(2). The 2 is not 1, and therein answer = factr(1) * 2;

There is a call of factr(1). The 1 is 1, and the call returns 1.

Therefore, factr(1) * 2 is actually 1 * 2
and call to factr(2) returns 2.

Therefore, factr(2) * 3 is actually 2 * 3
and call to factr(3) returns 6.
Without variable answer, the self-decrementing of n might be clearer as in the 'orthodox' version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

int factorial(int n);

int main()
{
    int aNumber;
    std::cout << "Enter number for factorial: ";
    std::cin >> aNumber;
    std::cout << "Factorial of : " << aNumber << " is " << factorial(aNumber) << '\n';
    
    return 0;
}

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


Enter number for factorial: 5
Factorial of : 5 is 120
Program ended with exit code: 0
I still seem to be really struggling to understand what is going on. Maybe my issue is coming from the return statements, since i have only really seen them when they are returning at the end of a function, so I am at a bit of a loss at what they are doing here. For instance, when the first return is executed return (1) it skips the rest of the statements in the function (which does make sense to me) but then, when it reaches the end of the block it returns back to the statement answer = factr(n - 1) * 2 or return n * factorial(n - 1); if i use againtrys method. Why is this, why does the code execution move upwards/backwards?
I think you're getting confused because factr() prints something after the recursive call.

Here is a version that prints when it enters factr() and when it leaves. I've also changed main() to call factr() before doing any output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

using namespace std;

int factr(int n);

int main()
{
	int factorial;
	cout << "Enter number for factorial \n";
	cin >> factorial;
	int ans = factr(factorial);
	cout << "Factorial of : " << factorial << " is " << ans << '\n';

 	return 0;
}

int factr(int n)
{
	int answer;
	cout << "Entering factr(" << n << ")\n";
	if (n == 1) {
	    answer = 1;
	} else {
	    answer = factr(n - 1) * n;
	}
	cout << "Leaving factr(" << n << "). Answer=" << answer << "\n";
	return(answer);
}

Enter number for factorial
3
Entering factr(3)
Entering factr(2)
Entering factr(1)
Leaving factr(1). Answer=1
Leaving factr(2). Answer=2
Leaving factr(3). Answer=6
Factorial of : 3 is 6

Here's another explanation.

What is happening is the function doesn't return to the call in main until all the sub-calculations are complete.
I would suggest you to execute your code step by step using a debugger so you may see the call stack

> why does the code execution move upwards/backwards?
it doesn't
you call a function, the function executes and ends, and then you continue to the next line
1
2
3
4
5
6
foo():
   a()
   b()
   c(d())
   e(f(), g())
   h()
say that you are in foo(), first line is a(), it calls the function, does whatever it does and returns
so the next line is b()
then you have c(d()), first call d() and then call c() using the returned value
same for e(), first executes f and g and pass whatever they return to e
then you reach h()

it just that in your case the function have the same name: factr(n=3) calls factr(n=2) that calls factr(n=1)
so in line 22 you have answer = factr(n - 1) * n; when the recursive call ends, the next line to execute is line 23 cout << answer << "\n";


notice that three different variables called `n' are created, they are independent of each other, they just happen to have the same name
(each function call is a word on its own)
Thank you dhyayden, your version has helped me follow through the code better, but I still am at a loss.

Using this version, since it is easier for me to understand and follow, why when answer is 1, and n is equal to 1, (when n==1 first time) does n then equal 2 in the statement answer = factr(n - 1 ) * n ? n was equal to 1, where did 2 come from? Even after the calculation it would have been (1 - 1) * 1.

And then the next time n = 3, when n and answer was 2, and the calculation for answer would have been (2-1) * 2.



new version from dhayden

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

int factr(int n);

int main()
{
	int factorial;
	cout << "Enter number for factorial \n";
	cin >> factorial;
	int ans = factr(factorial);
	cout << "Factorial of : " << factorial << " is " << ans << '\n';

	return 0;
}

int factr(int n)
{
	int answer;
	cout << "Entering factr(" << n << ")\n";
	if (n == 1) {
		answer = 1;
	}
	else {
		answer = factr(n - 1) * n;
	}
	cout << "Leaving factr(" << n << "). Answer=" << answer << "\n";
	return(answer);
}
because three different variables called `n' are created
each time you call factr() a new variable is created
because three different variables called `n' are created
each time you call factr() a new variable is created


Ok that helps, I should have realised that was happening. But I am still not sure where the numbers are coming from then, I am not passing in 2, or 3?

Also apologies, I had not noticed your last message before I sent my previous.
Main calls factr(3).
factr(3) calls factr(2)
factr(2) calls factr(1)

At this point you have main() -> facrt(3) ->factr(2) -> factr(1)

Now factr(1) returns 1. Using your line numbers, that means control returns to line 26 in the call to factr(2).

factr(2) sets answer = 1*2. It's important to realize that this "answer" variable is local to this specific call to factr. Each call to factr() has it's own copy of n and answer.

factr(2) returns its answer (2). Control returns to line 26 in the call to factr(3).
factr(3) sets answer = 2*3.
factr(3) returns 6.

Control returns to line 12 in main() where the program assigns 6 to ans.

You may be getting confused by not realizing that each call to facrt() has it's own distinct parameters, local variables, and return address.
OK I have figured out where my issues are. I still do not fully understand it, but I know at least what I am misunderstanding now. I failed to grasp the concept that (try to explain the best way I can) when factr was being called it was like putting it into a queue and then feeding those numbers back in once n was equal to zero, and that is where those numbers are coming from that I couldnt figure out (At least from what I am gathering now).


I doubt many people could misunderstand this as much as I did, but if anyone else comes across this, I found this video explains what I was stuck with pretty well https://www.youtube.com/watch?v=XkxV4gkWak8&t=206s
its a stack, not a queue.
If you have had data structures or gone over what a stack is, recursion is just like a loop with a free (hidden) stack data structure that you can use (indirectly, by making the recursive calls).

factorial does not matter that its a stack or queue (the order of the multiplication is not critical) but many other recursive functions do rely on the innate reversal (or, "go to the end, then back track") of the input and the order does matter for those algorithms. Its critical to understand that if given 5, it multiplies 2,3,4,5 and not 5,4,3,2 because later the order will matter and stacks go in reverse.

loads of people struggle with this the first time. This is partly because its often taught poorly, in a confusing way, and partly because its not an easy concept at first. Worse, many examples are pointless (factorial is a good one; you can do that with a loop or a lookup table, so recursion is overkill and all a student sees is convoluted code for the sake of writing convoluted code) so its hard to see when using this is handy from the early examples.
Last edited on
its a stack, not a queue.
If you have had data structures or gone over what a stack is, recursion is just like a loop with a free (hidden) stack data structure that you can use (indirectly, by making the recursive calls).


This is partly because its often taught poorly, in a confusing way, and partly because its not an easy concept at first.


It is a book I am learning from that is for beginners, and it has not spoke about data structures yet, so I do not think I am expected to know that yet. Could I ask your opinion regarding this? The book has basically just said what recursion is and gave this example and that is all. I have still to cover more indepth about functions, still to cover classes, qualifiers, enumerations, inheritance etc, in your opinion am I at a point I should go and learn more about recursion, or is that too advanced and I should still be learning these topics from the book first (I am thinking, that the book didnt go into a lot of detail about recursion for a reason, maybe)

For more info what I have covered in the book is an introduction to functions, arrays and pointers, control statements and data types
honestly if I were learning c++ today I would try to get a book that goes over the basics rather quickly (loops, if / else /switch, functions) and then jump into using the STL (vector, string focused for now) then move to basic objects (classes), then advanced classes (inheritance, templates, virtual and polymorph concepts) and then backtrack to pick up less used things like arrays (which you will learn all you need in the vector section anyway) and pointers (be sure it teaches smart pointers and newer styles, not a bunch of C pointer style stuff).

recursion is not all that advanced. In a nutshell, its a loop with a stack structure. Its just hard to get your mind around seeing it that way. It isnt that important early on. You will find it useful to do little things (eg, reverse a string, which c++ already provides anyway) with a line or two of code, or traverse a tree (a practical and useful problem). 95% of the time I see recursion its a tree, a school problem (like factorial) for the sake of it, or a cute-problem, like programming contest stuff, or how to write something clever in 1 line instead of 5 lines.

That said, don't waste a lot more time on recursion. If you understand the factorial, you can move on.

data structures is aside from coding and taught apart usually. c++ has most of the data structures in the language (the stl again). But you do need a basic understanding of what a stack, queue, list, tree, array all are and when to use each. Coding your own can help this understanding, which is what that book or class would be about, but as long as you can use the ones provided and know the differences, the quick path can skip all that (maybe code a tree and skip the others would be very good practice).
Last edited on
Putting recursion to one side, a good source of info/explanation/samples with a similar pathway is right here - even data structures.
http://www.cplusplus.com/doc/tutorial/
Topic archived. No new replies allowed.