While I recognize that this is somebody else's code, there are a few things in here which are bad practice - Best I tell you now while you're learning rather than later. Note that none of them print anything until you hit the guard ( None) at which time, things get printed from the back to front as the print_backward that received node 'c' must return before the print_backward that received node 'b' can print (because the print statement is after the function call) and so on. Your nodes look something like this: node1 node2 node3Īt the first call to print_backward, the variable list has the value 'a', subsequent calls to print_backward move one further down the line. In this case, that means that the print list part won't execute until all of the later elements have been printed first (in reverse order), thus giving you the list elements printed backwards. While the function is called first on the earlier elements, the part that actually prints that element comes after the recursive call, so it won't actually execute until that recursive call finishes. Print Node3 #now the third invocation finishes. We can now start unwinding as this is the base case: Print_backward(None) #calls itself on None. Print_backward(node3) #calls itself on next node Print_backward(node2) #calls itself on next node Take a look at this representation of what happened: print_backward(node1) #first call to print_backward This means that the 'instance' of print_backward created when you call it on the last element is the first one to finish, and thus the last element is the first one to be printed, followed by the second to last, third to last, etc., until the original function finally exits. currently, print_backward has been called on each element of the list, and it will now 'unwind', finishing the most recent calls first and the earlier calls last. The cool stuff usually happens on the way back as we unwind the recursive stack of function calls. The base case is the situation where no further breaking down the of program is necessary in this function, the base case is when there is nothing to print, in which case we just leave without doing anything with return. As the function continues, it builds up a bunch of calls until it finally gets to the base case. Sometimes I find it easier to think of recursion as merely constructing a list of calls to be made in a certain order. Downey also points out this problem later in the same chapter. Note: Several people below have pointed out that this function is badly designed since, given any list, we cannot show that it will always reach the base case. Wouldn't calling "list.next" as the value of print_backward simply give you "b c"? But I don't understand how the recursive call in the following function allows one to print the linked list backwards. def printList(node):Īll very straightforward. To print the linked list, we use another of Downey's functions. We give this class the following cargo and link values: #cargo These are set to None initially.ĭef _init_(self, cargo = None, next = None): #initialize with cargo (stores the value of the node) I'm working through Downey's How To Think Like a Computer Scientist and I have a question regarding his print_backward() function for Linked List.įirst, here's Downey's implementation of a Linked List in Python: class Node:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |