I saw this code:
def list_length(my_lis):
if mylist:
return 1 + list_length(my_lis[1:])
return 0
This code counts the number of elements in the list recursively without using len function. Can someone please explain the list_length(my_lis[1:]) and how it gets added to 1 because from my understanding, my_lis[1:] gives the list without the first element. So how can this give the number of elements in a list?
Ahh recursion, tends to make things more complex than they need to be, but it's still cool!
Let's add some debug code to see what is happening
def list_length(my_lis):
if my_lis:
print(my_lis)
length = list_length(my_lis[1:])
print(str(my_lis) + " returning 1 + " + str(length))
return 1 + length
print("Empty List! Return 0")
return 0
test_list = ['1', '2', '3', '4']
answer = list_length(test_list)
print("Answer: " + str(answer))
This will output:
['1', '2', '3', '4']
['2', '3', '4']
['3', '4']
['4']
Empty List! Return 0
['4'] returning 1 + 0
['3', '4'] returning 1 + 1
['2', '3', '4'] returning 1 + 2
['1', '2', '3', '4'] returning 1 + 3
Answer: 4
Notice how we only reach the base case (return 0) after the list is empty. Also notice that the number doesn't start going up until AFTER we hit the base case. Only after we reach an empty list can we start going back up the chain and counting 1 + whatever the last function got.
This goes as follows:
my_lis is not falsy (assumes non-empty list)This goes on until my_lis[1:] returns None, in this case instead of returning 1 we will return 0 and we do not trigger another recursive call.
Going from the innermost instead:
my_lis is empty, return 0my_lis is not empty, return 1 + 0my_lis is not empty, return 1 + (1 + 0)my_lis is not empty, return 1 + (1 + 1 + 0)This is how you end up with a list length.
Consider
my_lis = [1,2,3]
if condition satisfies because list isn't empty so returns 1+list_length(my_lis[1:]) meaning my_lis[1:] means [2,3] . So to generalize it you are decreasing length of list by one, that is you count the first element and ignore the first element.
return 1+ list_length(my_lis[1:]) #my_lis=[2,3]
return 1+ 1+ list_length(my_lis[1:]) #my_lis=[3]
return 1+ 1+ 1+ list_length(my_lis[1:]) #my_lis=[]
return 1+ 1+ 1+ 0
list_length(my_lis[1:])should give the length of that list, right? Now, compared to the original list, how long is that? If you add 1 to that result, what do you get? What exactly is the conceptual difficulty here?