python recursive list questions

Question

1.I came across this code: Python Recursion and list

def search(lst, key):
    if not lst:         # base case: list is empty
        return False
    elif lst[0] == key: # base case: current element is searched element
        return True
    else:               # recursive case: advance to next element in list
        return search(lst[1:], key)

Can the recursive search start from the first element as search(lst[0:],key)? Why is the first element treated separately?

2.Why is this a recursion?

selfref_list = [1, 2, 3]
selfref_list.append(selfref_list)

Upvoted as it is a good question for those who are new to recursion in programming. — Ozgur Vatansever
– Ozgur Vatansever, Commented Apr 30, 2016 at 18:42
2. Isn't really a recursion, this is called a cyclic or circular object--an object that contains a reference to itself. In other words, your list contains a reference to itself and that's how it became cyclic. — GIZ
– GIZ, Commented Apr 30, 2016 at 18:57

DWilches · Accepted Answer · 2016-04-30 18:57:27Z

5

About the first question:

If you start the recursion as search(lst[0:], key) then you will enter an infinite recursion. Notice that for the recursion to stop you need to have each time a smaller list than before and that is the case with search(lst[1:], key).

Also, as to why the first element is treated separately, notice you need to perform the comparison against key one element at a time, and that element is lst[0].

So in this recursion, you divide the problem in two: (1) you check if some element of the list is equal to your key (this element is always the first element of the current list), and (2) a recursive call in the rest of the list.

About the second question:

This isn't a recursion:

selfref_list = [1, 2, 3]
selfref_list.append(selfref_list)

What those lines do is to create a list where the 4th element is the same list:

>>> selfref_list == selfref_list[3] 
True

But that is not related to recursion in functions.

edited Apr 30, 2016 at 18:57

answered Apr 30, 2016 at 18:41

DWilches

23.4k17 gold badges82 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

GIZ Over a year ago

I agree with your answer except for the last part where selfref_list.append(selfref_list); OP was ambiguously asking about circular (cyclic) objects.

kpie Over a year ago

I think you need to look more broadly into the theme of recursion in languages. The conjugation of the concept does provide for the opportunity to not discus this question fully, but I would rather people really think about this one. Also this en.wikipedia.org/wiki/Recursive_data_type

jtitusj · Accepted Answer · 2016-04-30 18:45:53Z

1

For the first question, in the first line, def search(lst, key). that is, every time the function is called, it will use the entire lst which is the same as lst[0:]. Now, the reason that you have

    else: # recursive case: advance to next element in list
        return search(lst[1:], key)

is to define what happens after the current first element has been traversed. Basically, it says, "after the first element has been checked, continue with checking the rest of the elements starting with the next element."

answered Apr 30, 2016 at 18:45

jtitusj

3,1043 gold badges26 silver badges40 bronze badges

Comments

kpie · Accepted Answer · 2016-04-30 19:31:03Z

1

Why is the first element treated separately: Because each instance of your recursive method does part of your job, the function must check an element from the array. The First element or lst[0] will be the only element left when you call the function for a list with one element so why not just check it every time the list isn't empty?

Why is this a recursion?

selfref_list = [1, 2, 3] selfref_list.append(selfref_list)

In the most literal sense it is not recursion. Rather the data type is recursive, meaning that an object may include itself in an instance of the same object type. Or in more formal mathematical terms a node type in a grammar tree is permitted to have an outgoing edge to another node of similar type...

recursive grammar

recursive data Type

edited Apr 30, 2016 at 19:31

answered Apr 30, 2016 at 19:07

kpie

11.2k7 gold badges33 silver badges53 bronze badges

Collectives™ on Stack Overflow

python recursive list questions

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related