Why does this function print the linked list back?

Question

I work through Downey, how to think like a computer scientist, and I have a question regarding its print_backward () function for Linked List .

First, here is the implementation of the Downey linked list in Python:

class Node: #initialize with cargo (stores the value of the node) #and the link. These are set to None initially. def __init__(self, cargo = None, next = None): self.cargo = cargo self.next = next def __str__(self): return str(self.cargo) 

We give this class the following cargo values ​​and references:

  #cargo node1 = Node('a') node2 = Node('b') node3 = Node('c') #link them node1.next = node2 node2.next = node3 

To print a linked list, we use another Downey function.

 def printList(node): while node: print node, node = node.next >>>printList(node1) >>>abc 

Everything is very simple. But I don’t understand how the recursive call in the following function allows you to print the linked list back.

 def print_backward(list): if list == None : return print_backward(list.next) print list, >>>print_backward(node1) >>>cba 

Wouldn't it call "list.next" since the print_backward value just gives you "bc"?

Note. Several people below indicated that this feature is poorly designed, because, given any list, we cannot show that it will always reach the base case. Downey also points out this problem later in the same chapter.

Answer 1

In the direct print version, it prints each node before making a recursive call. In the reverse print version, it prints each node after making a recursive call.

This is no coincidence.

Both functions are overwritten until the end of the list is reached. The difference is whether printing occurs during or after this process.

Functional calls use the stack, the last data structure that remembers where the computer executed the code when the function was called. What is pushed onto the stack in the same order occurs in the reverse order. Thus, the recursion is "unwound" in the reverse order of the original calls. Printing occurs during the unwinding process, i.e. After the completion of each recursive call.

Answer 2

 def print_backward(list): if list == None : return print_backward(list.next) print list, 

Wouldn't it call "list.next" since the print_backward value just gives you "bc"?

No; what happens when a-> b-> c is passed print_backward:

"[bc]" is passed to print_backward, and then "a" is printed. But "print_backward", before printing "a", calls itself. So:

• [abc] is not None, so b-> c is passed print_backward
  • [bc] passed print_backward
    • [c] passed print_backward
    • None passed to print_backward
      • which returns
    • and then printed "c"
  • and then "b" is printed
• and then printed "a"
• quit smoking.

Answer 3

If the list is not None, it calls print_backward, and then prints the first element of the list. Expanded, this, of course, is what happens. You can see that when calls begin to return, “c” is printed, then “b”, then “a”.

It looks like when actually printing the list, it prints the first node

 print_backward(list='a','b','c') print_backward(list='b','c') print_backward(list='c') print_backward(list=None) list is None, so return print 'c' print 'b','c' print 'a','b','c' 

Answer 4

Sometimes it’s easier for me to think about recursion by simply creating a list of calls that need to be made in a specific order. As the function continues, it creates a bunch of calls until it finally gets into the base register. The main case is a situation when further program splitting is not required; in this function, the base register is when there is nothing to print, in which case we simply leave without any action with return .

Cool stuff usually happens on the way back when we unwind a recursive stack of function calls. Currently, print_backward is called for each item in the list, and now it is "unwound", ending the most recent calls first and the previous ones last. This means that the " print_backward " instance created when you call it on the last item is the first to be completed, and thus the last item is the first to be printed, and then second to last, from third to last, etc., until the final function completes.

Take a look at this view of what happened:

 print_backward(node1) #first call to print_backward print_backward(node2) #calls itself on next node print_backward(node3) #calls itself on next node print_backward(None) #calls itself on None. We can now start unwinding as this is the base case: print Node3 #now the third invocation finishes... print Node2 #and the second... print Node1 #and the first. 

While the function is called first on earlier elements, the part that actually prints this element comes after the recursive call, so it will not actually be executed until the recursive call ends. In this case, this means that part of the print list will not be executed until all later items are printed first (in reverse order), so you get the items in the list printed back .: D

Answer 5

It uses recursion. It "fastens" all the way to the end, then prints each item as each call returns. Because the first to get the stamp is the very last, it prints the list back.

Answer 6

Not. There are two types of recursion:

• Tail recursion: if after returning the function there is nothing to do except return its value. Calling functions is not performed.
• A recursion that first finds the base register (in this case null , then the reverse process processes the list). Each function call is pushed onto the stack for subsequent processing. In your example, the function is pushed onto the stack as 'a'->'b'->'c'->null , and then, when the stack is pushed, the author showed that by printing back: `if null return: print 'c' → print 'b' → print 'a'

In your case, the author demonstrated a different concept of recursion and used this to print the list back.

Answer 7

Your nodes look something like this:

 node1 node2 node3 'a' => 'b' => 'c' => None 

The first time print_backward called, the print_backward variable is set to 'a' , subsequent calls to print_backward move further down the line. Please note that none of them prints anything until you press the None print_backward , at this time everything will be printed from the back side, since the print_backward received by node 'c' must return before print_backward , which is received node 'b' can print (because the print statement is after a function call), etc.

Although I understand that this is someone else's code, there are a few things that are bad practice. Best of all, I will tell you now while you are studying, and not later. Firstly, do not use list as a variable name, as this is the name of a built-in function / type in python. secondly, the equality test if obj == None best done with if obj is None , finally, it is always useful that your classes inherit from object ( class node(object): , since this makes it a new-style class.