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, Apr 30 '16 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, Apr 30 '16 at 18:57

Daniel · Accepted Answer · 2016-04-30T18:57:27.410

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.

I agree with your answer except for the last part where `selfref_list.append(selfref_list)`; OP was ambiguously asking about circular (cyclic) objects. — GIZ, Apr 30 '16 at 18:55
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 https://en.wikipedia.org/wiki/Recursive_data_type — kpie, Apr 30 '16 at 19:13

score 1 · Answer 2 · answered Apr 30 '16 at 18:45

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."

kpie · Answer 3 · 2016-04-30T19:31:03.603

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

python recursive list questions

3 Answers3