0

If you have a list = [1,2,3,4,5]

how would you recursively calculate the length of that list without using len(list)?

myarray = [1,2,3,4,5]

def mylist(myarray):
    if (myarray == []):
        print ("The list is empty")
        return 
    return 1 + ?

Don't want to use len but just add 1 each time there exists a value in list. How would I do that?

Autoplectic
  • 7,566
  • 30
  • 30
Eric
  • 235
  • 3
  • 10
  • 17
  • Please replace `(myarray == [])` with `not myarray`. – Seth Johnson Apr 18 '11 at 00:42
  • I can't help but ask: why on earth would you want to do that? DTing's accepted answer has O(N**2) complexity which is just horrible, compared to the standard len function (very short constant time for Python list) – gurney alex Apr 18 '11 at 06:43

2 Answers2

8
>>> def list_length(L):
...     if L:
...         return 1 + list_length(L[1:])
...     return 0
... 
>>> list_length(myarray)
5
>>> list_length([])
0
>>> list_length([1]*4)
4
>>>

If the list has elements, return 1 + the length of the list minus one element.

You can do this a couple different ways, but slicing [:1] or [1:] will give you the elements minus the last or first respectively, makes sense.

If the list has no elements, return 0

dting
  • 38,604
  • 10
  • 95
  • 114
  • The slice syntax in this explanation contains an error. One would use `[:-1]` to return the list minus the last element. I would have edited this, but apparently edits must be of at least 6 characters. – vschum Jan 21 '20 at 20:28
-2

Use a recursive function.

Basically call the function again and add the count returned by it to the result. Important thing is to make sure you exit (return) when the function has nothing to do.

Check out this post Python recursion and return statements

Community
  • 1
  • 1
Devraj
  • 3,025
  • 24
  • 25