473,594 Members | 2,678 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

recursion and linked lists

Can someone explain to me how this works:

def printBackward(l ist):
if list == None: return
head = list
tail = list.next
printBackward(t ail)
print head,

printBackward(n ode1)

3 2 1
The printable value of node1 is 1, node2 is 2 and node 3 is 3.

node1.next is node2, node2.next is node3 and node3.next is None.

This might be painfully obvious, but I don't understand when the print
statement is getting called. If you call printBackward with node1, then
you skip the if statement, head becomes node1, tail becomes node2 and
then you call printBackward again with node2. During this call you call
printBackward again with node 3 and then the next time the if statement
returns. So when does the print happen, and how does it print 3
different values? It seems like you wouldn't get to it until the last
time printBackward returns, and 'head' at that point would be 3, which
is the first number printed. But doesn't it stop at this point? Where do
2 and 1 come from?

Thanks!
Apr 1 '06 #1
3 1704
I V
John Salerno wrote:
The printable value of node1 is 1, node2 is 2 and node 3 is 3.

node1.next is node2, node2.next is node3 and node3.next is None.

This might be painfully obvious, but I don't understand when the print
statement is getting called. If you call printBackward with node1, then
you skip the if statement, head becomes node1, tail becomes node2 and
then you call printBackward again with node2. During this call you call
printBackward again with node 3 and then the next time the if statement
returns. So when does the print happen, and how does it print 3
different values? It seems like you wouldn't get to it until the last
time printBackward returns, and 'head' at that point would be 3, which
Each time printBackward gets called, it has it's own separate 'head'
variable. We could imagine they're all separate variables head1 for the
first time printBackward is called, head2 for the second, and so on.
The first time printBackwards gets called, it's local 'head' variable
(head1) gets set to 1, and so on.
is the first number printed. But doesn't it stop at this point? Where do
2 and 1 come from?


Note that print gets called after _each_ time that printBackward
returns. So, as the different calls to printBackward return, they print
whatever 'head' was set to in that invocation. Now, logically enough,
the last call to printBackward is the first to return, so the last
value of 'head' is printed first, and so in in the reverse order of the
list. Maybe this will help you visualize what is going on:

call printBackward with arg [1, 2, 3]
head1 = 1
call printBackward with arg [2, 3]
head2 = 2
call printBackward with arg [3]
head3 = 3
call printBackward with arg None
return
print head3 ( == 3)
return
print head2 (== 2)
return
print head1 (== 1)
return

Apr 1 '06 #2
I V wrote:

Note that print gets called after _each_ time that printBackward
returns. So, as the different calls to printBackward return, they print
whatever 'head' was set to in that invocation. Now, logically enough,
the last call to printBackward is the first to return, so the last
value of 'head' is printed first, and so in in the reverse order of the
list.


Oh, that helps! Now I'm starting to understand when exactly it returns
each time.
Apr 1 '06 #3
On 01/04/06, John Salerno <jo******@nospa mgmail.com> wrote:
I V wrote:

Note that print gets called after _each_ time that printBackward
returns. So, as the different calls to printBackward return, they print
whatever 'head' was set to in that invocation. Now, logically enough,
the last call to printBackward is the first to return, so the last
value of 'head' is printed first, and so in in the reverse order of the
list.


Oh, that helps! Now I'm starting to understand when exactly it returns
each time.


The way I got my head round this was to think of namespaces (I'm not
sure how true this is though).

I think of the first head variable as being:

printBackward.h ead

When it calls printBackward from within the first printBackward, thye
second variable is:

printBackward.p rintBackward.he ad

and so on. It helps to keep it clear that they are entirely different.

Ed
Apr 7 '06 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
8243
by: Kakarot | last post by:
I'm gona be very honest here, I suck at programming, *especially* at C++. It's funny because I actually like the idea of programming ... normally what I like I'm atleast decent at. But C++ is a different story. Linked lists have been giving me a headache. I can barely manage to create a single/doubly linked list, it's just that when it gets to merge sorting or searching (by reading shit data from text files), I lose track.
7
4814
by: Chris Ritchey | last post by:
Hmmm I might scare people away from this one just by the title, or draw people in with a chalange :) I'm writting this program in c++, however I'm using char* instead of the string class, I am ordered by my instructor and she does have her reasons so I have to use char*. So there is alot of c in the code as well Anyways, I have a linked list of linked lists of a class we defined, I need to make all this into a char*, I know that I...
11
2074
by: hana1 | last post by:
Hello guys, I just have a quick question about C++. I am moving from Java to C++. And as many of Java users know, all linked list and trees are already implemented and you just have to instantiate them. Is tehre a simiar thing in c++, or I have to write my own Linked list class? Thank you very much Cheers
1
418
by: Anthony Moss | last post by:
Does anyone know a good web site that explains linked lists in C thanks Anthony
3
3261
by: s_subbarayan | last post by:
Dear all, 1)In one of our implementation for an application we are supposed to collate two linked lists.The actual problem is like this: There are two singularly linked lists, the final output will be a "perfectly shuffle" of the lists together into a single list. The new list should consist of consecutively alternating nodes from both lists.Note that both these linked lists have same kind of data structure in their nodes.
6
3988
by: paudirac | last post by:
Hi, I need to maintain N linked lists where N is determined at runtime. The linked lists are defined as follows, struct linked_list { int data; struct linked_list next; }
17
1769
by: Foodbank | last post by:
Hi, I have to write a program that will use linked lists to print the number of unique words, total words, and the most frequent word from a text file. I've gotten a decent amount of it done except for the linked lists. I did not paste my code that tells the machine what a word is, it works fine and it'll be easier to read that way without it. Below is the code: //****code from here to next section is good, I don't need help
3
472
by: Little | last post by:
Could someone tell me what I am doing wrong here about declaring mutiple double linked lists. This is what the information is for the project and the code wil be below that. Thank your soo much for your assitance in helping me solve this problem. Information: Create 4 double linked lists as follows: (a) A double linked list called NAMES which will contain all C like
51
8607
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort for linked lists, I couldn't find one. I read something about Mcilroy's "Optimistic Merge Sort" and studied some implementation, but they were for arrays. Does anybody know if Mcilroys optimization is applicable to truly linked lists at all?
23
3850
by: Just Another Victim of the Ambient Morality | last post by:
I'm looking for a linked list implementation. Something iterable with constant time insertion anywhere in the list. I was wondering if deque() is the class to use or if there's something else. Is there? Thank you...
0
8246
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8368
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
6652
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
5738
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5404
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
3895
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2383
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1476
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1205
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.