This is recurion program Following program output is 321123 i don't know how its work?

Question

def printfun(test):
if(test<1):
return
else:
print(test)
printfun (test-1)
print(test)
return
test=3
printfun(test)

Answer 1

David Carroll definitely there seems some confusion because when I was learning recursion, I was taught that when the function call is at the end of the function then it is a head recursion.

If you remove the last print(test) in the function, it will give you that. And if you remove the first print(test) then the function call comes first which will give you a tail recursion.

https://www.geeksforgeeks.org/types-of-recursions/

This is only from my understanding, please correct me if I am wrong.

Answer 2

printfun(3) => test<1 false so in else part print(3) and call printfun(3-1) #Now resume here in stack test =3 now, note that. Next go to recent function call

printfun(2) => test=2 <1 false so in else part print(2) and call printfun(2-1) # test value pushed to stack for later retrieval, control goes to new function call printfun(1),new function test value is 1.

printfun(1) =>test 1<1 false so prints 1 in else part and call printfun(1-1), test=1 is pushed to stack.
printfun(0) =>test=0<1 is true now so just execute if part return statement so control goes called previous function i.e printfun(1) in that test=1. From the stack the value popped so control goes to next statement of calling function statement that is print(test), note that test=1 here so prints 1. And called return statement so now the recent last function call printfun(1),
Recursively next printfun(2) is completed after printing print(2)
Next Fisrt function printfun(3) is completed by printing 3.
So output is 321123.

Answer 3

Avinesh To eliminate confusion, I wanted to clarify that the recursive function in this post is neither head nor tail recursion.

Those have very specific characteristics not reflected in this example.

Answer 4

It is basically a head and tail recursion happening one after the other.
Jayakrishna🇮🇳 has explained it well. You must draw the stack and see it for yourself to understand it better.

Answer 5

Avinesh I'll respond after each notable comment:

----
Comment #1:
"I was taught that when the function call is at the end of the function then it is a head recursion."
--

That's unfortunate since this actually describes tail recursion.

----
Comment #2:
"If you remove the last print(test) in the function, it will give you that."
--

While removing the last statement would make this tail recursion, the fact that it exists is quite significant in disqualifying it to be tail recursion.

----
Comment #3:
“And if you remove the first print(test) then the function call comes first which will give you a tail recursion."
--

Technically, removing the first print(test) does nothing in changing the recursion type. Assuming you are trying to describe head recursion, the call to printfun(test-1) would need to be moved to the if true block.

Even if what you were taught were correct in how these are classified, any need for change would disqualify this for either type of recursion.

Hence, the reason for clarification.

Answer 6

David Carroll thanks for the clarification. I think I was really confused between the two.