Recursion in python functions -- confusion

[late347]

example code from python-course.eu

def factorial(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
        print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
        return res   

print(factorial(3))

Looking at the code I don't understand how the program is able to print so many "intermediate result for n" messages ...

when you call the function called factorial with parameter 3:

1. "factorial has been called with 3" is printed
2. if clause is negative
3. res = 3* (something...?) at this point the factorial is called again from inside itself with parameter 2 This step is a little bit confusing because I can't really deduce from the code immediately what value will be assigned to the variable res...
   
4. "factorial has been called with 2" is printed
5. if clause is negative
6. res = something and factorial is called with parameter 1
7. "factorial has been called with 1" is printed
8. if clause is positive.
9. at this point I think the program should probably come out from the line factorial(2-1)...
10. "intermediate result for 2*factorial(1) =2"" is printed
11. why doesn't the program just end there? I don't get it why the program prints the extra "intermediate result for 3*factorial(2)=6"

I know how factorial works in math and in my brain, but I can't seem to understand the extra message "intermediate result for 3* factorial(2)=6"

of course in real life the factorial of 3 is indeed as follows
3*2*1 = 6

 

[Ibix]

Recursion is easy to understand. You just need to understand recursion first.

The way I look at it is this - when you write a function, the computer sticks it in a filing cabinet somewhere. When you call the function, the computer takes a photocopy of the original and begins working its way through the instructions step by step. If it gets to a function call, it puts a post-it at the function call, puts the function to one side, and goes back to its filing cabinet and photocopier. If this next function has another function call inside it, it puts a post-it on this function, stacks it on top of the first function and goes back to the filing cabinet. If a function terminates, it chucks the photocopy in the bin and goes back to the top paper in its stack and carries on from where the post-it was.

Incidentally, this is why you get a "stack trace" when something crashes - the computer just tells you what functions it had stacked up and where the post-its were when it all went wrong.

Recursive functions are easy enough to understand like that. With your example of factorial(3), the computer takes a copy of the factorial() function, works through it until it gets to the call of factorial(n-1). That's a function call, so it sticks a post-it there, puts it aside and takes another photocopy of factorial(), this time working through it with argument n=2. Again, it gets to the call to factorial(), so it sticks a post-it and puts it aside, then takes another photocopy and works through it with argument n=1. This time there's no function call, so it returns the value 1, bins this copy of factorial() and goes back to the top function on its stack, which just asks it to return n times whatever factorial(n-1) returned - so 2*1=2 in this case. It bins this copy of the function and goes back to the remaining function in its stack, which returns n times the 2 that got returned - so 3*2=6 in this case. Then it prints the result.

Note that there are loads of function calls to print() and str() and __add__() etc. in your function, so the above is somewhat simplified. But it's the important bit.

 

[UsableThought]

@Ibix seems like he knows his stuff. I haven't done Python in a long time . . . but always enjoyed it. However I typically worked at a very simple level, and rarely thought beyond that.

The way I would think of this example is, the recursion is being driven by the "res = " statement where the function is called again. So there's a first recursion branch, which I would call the inner loop, where n does not yet equal 1 (producing the prints of "factorial has been called with"); and then once n = 1, we move to the second recursion branch, or outer loop, for the "intermediate" prints. Close?

Myself, I'm not sure I would have written a loop this way; I preferred to be explicit and verbose as opposed to implied and laconic. However even then, my first tries at loops in lengthy routines sometimes would puzzle me. If I couldn't quickly figure it out, I would often add temporary print statements to see if I could follow the execution by whether and when a temporary statement would print. I guess that's a brute force way of doing it, but it worked well for me.

 

[late347]

well, I'm not sure what the execution of the program is supposed to do with the "old and obsolete function calls" such as res=3*factorial(2)

Like...

factorial(3)

1. print (factorial called with 3)
2. negative if clause
3. proceed to calculate res= 3*(factorial 2)
4. print (factorial called with 2)
5. negative if clause
6. proceed to calculate res= 2*(factorial 1)
7. print (factorial called with 1)
8. positive if clause
9. proceed to (where did we come from again...? we DID come from res=2*factorial(1) and we definitively now know, that factorial of 1=1, therefore res=2*1=2
10. end program?

what I don't understand is that why should the program keeps backtracking from res= 2* factorial (1) -->into old and obsolete function calls such as factorial(3)
why would the program go back into that already executed line, which did not yield anything useful, except keep calling itself with parameter of 2 such that the parameter variable keeps getting smaller?

how can the line "intermediate result for 3 times factorial (2)" keep staying alive, instead of dying and not being executed as code?

 

[UsableThought]

why would the program go back into that already executed line, which did not yield anything useful, except keep calling itself with parameter of 2 such that the parameter variable keeps getting smaller?

This is why I suggest doing something with temporary "print" statements - you start to see what is actually happening & don't have to guess at the flow of execution.

Scripts are strict. They run the way they're supposed to, not the way we think or wish they should run; a computer language is not like humans, it has no concept of what is "useful". I am going to take a wild guess you haven't done much programming yet?

 

[late347]

This is why I suggest doing something with temporary "print" statements - you start to see what is actually happening & don't have to guess at the flow of execution.

Scripts run the way they're supposed to, not the way you think or wish they should run; a computer language is not like us, it has no concept of what is "useful". I am going to take a wild guess you haven't done much programming yet?

not with recursive function in python but yes I have done a little bit of programming with python

 

[UsableThought]

not with recursive function in python but yes I have done a little bit of programming with python

OK. A suggestion: trying to line up the program statements with program output by itself is not going to tell you anything. Whatever method you use, you want to get inside the machinery to follow actual execution. What it's doing = what it was told to do.

The only critical thing to understand here, I think, is that the res = statement defines that variable by calling the function again. That's what forces the recursion. The recursion runs twice because of the if/else. So with this in mind, one thing you could do is, start at the top line & for each line, track the variable values & see how the line will respond. You can do this with paper & pencil; you can walk through both loops that way if you focus on one line at a time. Also, level of nesting is crucial to follow recursion; it's easy to get this wrong by eye, even if the commands are properly indented. Again, inserting temporary print statements has been helpful for me in ruling out this sort of casual mistake.

 

[Mark44]

example code from python-course.eu

def factorial(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
        print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
        return res  

print(factorial(3))

Looking at the code I don't understand how the program is able to print so many "intermediate result for n" messages ...

when you call the function called factorial with parameter 3:

1. "factorial has been called with 3" is printed
2. if clause is negative
3. res = 3* (something...?) at this point the factorial is called again from inside itself with parameter 2 This step is a little bit confusing because I can't really deduce from the code immediately what value will be assigned to the variable res...

Step 3 seems to be the one you're having the most trouble with. The first time this function is called, with n set to 3, the if clause (or suite, in Python terminology) doesn't execute, but the else suite does execute. In the first line of the else suite the statement becomes res = 2 * factorial(2)., which calls the factorial function, this time with an argument of 2. At this time, with n = 3, the two statements that follow res = 2 * factorial(2) are not executed, and don't get executed until either of the return statements of a recursive call are executed.

To make it easier to understand what is going on, start with passing 2 to your factorial function. This will cause a recursive call to factorial(1), which will return 1, which will cause the call to factorial(2) to return 2 * 1, or 2. Once you understand how that is working, see if you can follow things through with an initial call of factorial(3).

 

[UsableThought]

Step 3 seems to be the one you're having the most trouble with.

Agreed.

res = 3* (something...?) at this point the factorial is called again from inside itself with parameter 2 This step is a little bit confusing because I can't really deduce from the code immediately what value will be assigned to the variable res...

This is why I suggested walking through the script line by line, with a pencil and paper. Start by feeding in a value for n. Keep track of the value for it and for res (once res is defined) before and after each line. If you keep track of the state of the variables, when you enter the line "res = n * factorial(n-1)", you will be able to feed the value of n-1 into the function again & start a fresh walk-through for that loop, on a separate sheet of paper. See what happens on that sheet of paper. Eventually you will find that you are returned to your first sheet of paper where you continue the walk-through to the end.

Or, as @Mark44 suggests, you can try small values to see the loops in miniature; or as I suggested, add in temporary print statements & see if they print where & when you expected, or differently.

 

[late347]

Step 3 seems to be the one you're having the most trouble with. The first time this function is called, with n set to 3, the if clause (or suite, in Python terminology) doesn't execute, but the else suite does execute. In the first line of the else suite the statement becomes res = 2 * factorial(2)., which calls the factorial function, this time with an argument of 2. At this time, with n = 3, the two statements that follow res = 2 * factorial(2) are not executed, and don't get executed until either of the return statements of a recursive call are executed.

To make it easier to understand what is going on, start with passing 2 to your factorial function. This will cause a recursive call to factorial(1), which will return 1, which will cause the call to factorial(2) to return 2 * 1, or 2. Once you understand how that is working, see if you can follow things through with an initial call of factorial(3).

But you are saying they will get executed from their respective points (n=some earlier value)? Especially since evidently the program does turn into backtracking from n=1, then the return throws the program into the [n=2, res=2*1, followed by the new print, followed by the return res statement.

I do know in principle how basic function returns work in python but this was little bit more difficult for me because the same function calls itself.

One source of confusion about that recursive program was that How was it possible for the program to remember the "earlier values of n, and res, and value of factorial(3) " which correspond to the correct value of n at that specific time (i.e. the respective value)?

Apparently the earlier values of n (n=4,n=3,n=2 etc...) apparently those values are not "wiped out" by the new values which should be assigned to the variable n from the next round of the call of factorial with the parameter (n-1)

From the conditions of if suite, inside the function... We definitely know that the value that is assigned to local variable n does become smaller. Until it gets the value 1. Somehow the program apparently remembers the earlier and bigger n- values also? And also the program is able to execute each respective print command for each earlier n-value.

If you input factorial (4)
Evidently what is happening is that the factorial(4) begins one avenue, but is detracked into another avenue with the call of factorial(3)
Again factorial(3) is detracked into another avenue of factorial(2). With factorial (2) it is detracked into factorial(1). FActorial(1) is computed and the program returns to [n=2, res=2*1=2]. Then there is the mysterious return...

Then apparently the program returns to [n=3, res=3*2=6], followed by print and returns to...
[n=4, res= 4*6] followed by print

I know that the return res apparently just returns the res value into the factorial BUT... that specific res value gets overwritten by the new calculation res=n*factorial(n-1). The last res value should be the correct factorial value also, and it is printed on its own, in the end. Next example shows this line of thinking

def factorial(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
        print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
        print("result value of",res)##it is here
        return res   

print(factorial(4))

 

[StoneTemplePython]

One source of confusion about that recursive program was that How was it possible for the program to remember the "earlier values of n, and res, and value of factorial(3) " which correspond to the correct value of n at that specific time (i.e. the respective value)?

[/code]

I have two thoughts here.

1.) It could be instructive to re-write the factorial function in a nearly identical way that uses an explicit stack. Comparing and contrasting the explicit stack approach vs the implicit stack in your recursive program can be quite instructive. The caveat here is, roughly speaking, you need to be somewhat familiar with depth first search to do this-- and I may be inadvertently swapping your problem for a much bigger one on here.

2.) Consider taking a look at Allen Downey's excellent and freely available Python texts. For this specific problem you may want to review Think Python's "Chapter 5. Conditionals and recursion". The Green Tea Press makes this text available here:

http://greenteapress.com/thinkpython/thinkpython.pdf

 

[Mark44]

But you are saying they will get executed from their respective points (n=some earlier value)? Especially since evidently the program does turn into backtracking from n=1, then the return throws the program into the [n=2, res=2*1, followed by the new print, followed by the return res statement.
[/quote]It's not clear to me what you're saying here. If you call factorial(2), it will call factorial(1), which is not recursive. factoria(1) returns 1, and the assignment statement res = 2 * factorial(1) can finally execute, storing 2 in res.

I do know in principle how basic function returns work in python but this was little bit more difficult for me because the same function calls itself.

Which is because of the recursive nature of this function. The situation is similar if you have a function A() that calls another function B() somewhere in the middle of A(). The statements in A() execute up to the call to B(), and then control transfers to B(). When B returns, execution in A() resumes where it left off. That's what's happening in your factorial() function.

One source of confusion about that recursive program was that How was it possible for the program to remember the "earlier values of n, and res, and value of factorial(3) " which correspond to the correct value of n at that specific time (i.e. the respective value)?

Because each call to any function has its own stack frame and variables. A variable n in one call to factorial() is different from the variable n in a different call to factorial().

Apparently the earlier values of n (n=4,n=3,n=2 etc...) apparently those values are not "wiped out" by the new values which should be assigned to the variable n from the next round of the call of factorial with the parameter (n-1)

 

[NTL2009]

Is this just to satisfy your own curiosity? If so, OK.

But if not, I'm the pragmatic type, and I would say "Just don't do that!". There are solutions that would not involve a recursive call, and they would be easier for others to understand, especially if someone else may have to maintain this code at some point.

I also wonder if there isn't some risk that this approach is enough of an 'edge case', that a different version or implementation of Python might give different results? That would be bad.

 

[jartsa]

How about this:

def factorial(n):
    print("I was asked to calculate factorial of "+ str(n))
    if n == 1:
        res= 1
    else:
        res = n * factorial(n-1)
    print("The result is " + str(res)+". After printing this message I return the result to whoever it was that called me.")
    return res  

print(factorial(3))

Or this:

def factorial(n):
    if n == 1:
        res= 1
    else:
        res = n * factorial(n-1)
    print("I was asked to calculate factorial of "+ str(n)+". The result is " + str(res) +". After printing this message I return the result to whoever it was that called me.")
    return res  
print(factorial(3))

 

[Mark44]

Is this just to satisfy your own curiosity? If so, OK.

But if not, I'm the pragmatic type, and I would say "Just don't do that!". There are solutions that would not involve a recursive call, and they would be easier for others to understand, especially if someone else may have to maintain this code at some point.

If @late347 is studying recursive functions, then advising him to write a version that doesn't use recursion is not good advice. I agree that in many instances recursive functions are to be avoided, but if the goal is to learn about how recursion works, this is a good one to learn with.

 

[NTL2009]

If @late347 is studying recursive functions, then advising him to write a version that doesn't use recursion is not good advice. I agree that in many instances recursive functions are to be avoided, but if the goal is to learn about how recursion works, this is a good one to learn with.

Agreed. But it wasn't clear to me that this was a learning exercise (that's why I asked). It seemed he just started out saying he was having a problem with this recursive example. I'm sometimes inspired by the "Gordian Knot" approach - instead of putting a lot of energy into solving a problem, find a way around the problem.

Sometimes the learning is good, and will pay off in the future. I guess I don't know if that is the case here.

 

[UsableThought]

Is this just to satisfy your own curiosity?

A good question. The OP says the code is an example from http://python-course.eu but hasn't said whether he's actually taking a course there.

There are solutions that would not involve a recursive call, and they would be easier for others to understand, especially if someone else may have to maintain this code at some point.

If this were really production code, comments could provide explanation for maintenance & are a good idea anyway. That seems a separate issue.

Consider taking a look at Allen Downey's excellent and freely available Python texts.

To me this is the best suggestion. Since the OP is still struggling despite all the attempts to help, maybe it would be best to just open up a good book & work through some clearly explained examples. Picking a wall to beat your head against is not always a good learning strategy.

 

[wle]

Agreed. But it wasn't clear to me that this was a learning exercise (that's why I asked). It seemed he just started out saying he was having a problem with this recursive example. I'm sometimes inspired by the "Gordian Knot" approach - instead of putting a lot of energy into solving a problem, find a way around the problem.

Sometimes the learning is good, and will pay off in the future. I guess I don't know if that is the case here.

Recursion is useful to learn and understand. It isn't a good way to write a factorial function in most languages because it is wasteful of memory (and can lead to a stack overflow), but there are certain problems where recursion is the most natural solution. For example, if you were writing code to visit all the nodes in a binary tree then the code needs to store somewhere which path it took down the tree to get to each node as it is being visited, and in a recursive solution that information is saved and maintained automatically in the hierarchy of recursive function calls.

 

[late347]

A good question. The OP says the code is an example from http://python-course.eu but hasn't said whether he's actually taking a course there.
If this were really production code, comments could provide explanation for maintenance & are a good idea anyway. That seems a separate issue.
To me this is the best suggestion. Since the OP is still struggling despite all the attempts to help, maybe it would be best to just open up a good book & work through some clearly explained examples. Picking a wall to beat your head against is not always a good learning strategy.

Well, I had come across some recursion type code on codewars.com but I didnt really find the point of it.

I sort of know how recursive function works with pen and paper... it's tedious to calculate. But, if you are able to e.g. tabulate the certain values then you can keep calculating in backtracking manner to the" first case"

We were not really taught much about recursion in python at school. I think our teacher at that time even recommended trying to avoid this kind of thing as 'best practises.'

We were not really taught what was the so-called stack frame with regards to function call. I guess our course was really about python basics and we had a substitute teacher there. But I think he still did a good job teaching lots of python basics.

I was a little bit unclear as to what happens to the earlier function call such as factorial(4) but the factorial(4) was sidetracked into a new stackframe with res=4×factlrial(3)

 

[UsableThought]

We were not really taught much about recursion in python at school. I think our teacher at that time even recommended trying to avoid this kind of thing as 'best practises.'

I never coded much with it myself, but I can hardly claim to have been hard-core. But I did write many programs that worked well over a span of 5 or 6 years, including an entire CGI-driven website for document management, and probably never had to use recursion. I like the comment #18 by @wle, above, where he suggests it's a good thing to learn & gives an example; that example sounds vaguely familiar to me, as I do remember reading in my books, way back then, about similar reasons for using recursion. Sometimes it's a natural fit. Not in your example, though; that looks to me like just a demo.

Although I like tutorial sites, I seem to learn best via books. When I was doing Python, I eventually acquired maybe 4 or 5 books on the language (in addition to asking questions on coding forums). I had already coded quite a bit in other scripting languages, and had even sold some scripts to clients for things they couldn't do themselves back then in the early days of web commerce; but these other languages were markedly inferior to Python. Discovering a real language with such depth was exciting. Once I had the basics down, I used to like browsing through my books to find examples of neat aspects of the language that I could put to use. I actually found it fun.