Can somebody explain me how the recursion works?

Question

I'm learning recursion, I have this python code:

def count(list):
if list == []:
return 0
return 1 + count(list[1:])

this code tells you how many items the list has, I really tried so hard to understand it but I can't, why the 1 in the return sentence is there?

somebody can explain me how the recursion works in this code?

Answer 1

I'm not well-versed in python but I do use recursion in Javascript.

With recursion, you always need to provide a way to decrement or increment to some final condition or you create an infinite loop.

In your example, the decrement is provided by list[1:]. This splices or chops off the first number in the list and passes that shortened list into the function again.
The other one (1) in the return statement allows you to tally the number of recursive function calls or loops that occur so you can count the items in your list.

Example: list = [1,1,1]

count(list);

Your first loop returns: 1 + count([1,1]),

Your second loop returns 1 + (1 + count([1])),

Third loop is 1 + (1 + (1 + count([]))) which equals 3. So you've successfully counted the items in your list and returned 3.

Hope this helps.

Answer 2

recursion calls another instance of the function until you reach a termination condition
Example: list = 'hello'
count(list) = 1 + count('ello)
count('ello') = 1 + count('llo')
count('llo)= 1+ count('lo')
so on
this simplifies to (1+1+1+1+1+0) so count('hello') would return 5

Answer 3

thx everyone

Answer 4

Try to read it backwards!

You start with the base case, which is what you will definitely end up with, right? So in this case you start with 0, when the list will be empty.

Now you go backwards, one step before: The list was one element long. You have your 0, now you add the 1, as is written there. You go back the next step, where the list was still two elements long, so you again add 1 (0+1+1=2), then you go back further, until the list is complete.

Since from zero towards all of the elements you add 1 each time to the initial 0, practically you just count how many elements are in there to start with.

In summary: 1.) You start with the base case return value, whatever it is; 2.) Then you do with this value whatever is written next to the recursive call (in this case 1+), 3.) for as many times the function is actually called.