def func(head)
if head is None:
return
print(head.data)
if head.next_element:
func(head.next_element.next_element)
print(head.data)
head = lst.get_head() # assume ‘list’ contains the contents above
func(head)
i think this code will output 1355,why this output 135531?
Disclaimer: I’m no educator, just someone is also studying this course.
I also had similar thought with you but I think I figured it out. If my understanding of recursion is correct, you have to include the 3 iterations of the last line “print(head.data)”. Only after the last recursion is completed, it will backtrack and execute that last line for every recursion.
1 , 3 , 5 is executed on the first “print(head.data)”. The last recursion reached base case. Now execute the last “print(head.data)” for every recursion in the order starting from the last recursion. Last recursion’s value is 5 then 3 then 1. So eventually the output will be 1, 3, 5, 5, 3, 1.
Hope this make sense and feel free to correct me.
@Chee_Zhiquan is absolutely correct. Every time you call recursion, you print the current node’s value before it. And once, the recursion returns, the same node value is printed again.
So for input: 1->2->3->4->5->6
It iterates through recursion in the order 1 3 5.
At node value 5, it returns because there is no node after it’s next node. So before it returns it prints the value of 5 again and returns to the function that called it recursively which would be the function for node 3. Consequently, all nodes print their values again and exit their functions leading to an order of 5 3 1.
Best Regards,
Ali Ahad | Developer Advocate
Educative.io