CODEWITHSUNDEEP
pythonpython-3.xrecursion
Gagan Deep Singh
Gagan Deep Singh

Reputation: 457

Counting Total Number of Elements in a List using Recursion

The Problem:

Count the number of elements in a List using recursion.

I wrote the following function:


def count_rec(arr, i):
    """
        This function takes List (arr) and Index Number
        then returns the count of number of elements in it 
        using Recursion.
    """
    try:
        temp = arr[i]  # if element exists at i, continue
        return 1 + count_rec(arr, i+1)
    except IndexError:
        # if index error, that means, i == length of list
        return 0

I noticed some problems with it:

  1. RecursionError (when the number of elements is more than 990)
  2. Using a temp element (wasting memory..?)
  3. Exception Handling (I feel like we shouldn't use it unless necessary)

If anyone can suggest how to improve the above solution or come up with an alternative one, It would be really helpful.

Upvotes: 1

Views: 476

Answers (3)

Bobby Ocean
Bobby Ocean

Reputation: 3328

What you have is probably as efficient as you are going to get for this thought experiment (obviously, python already calculates and stores length for LIST objects, which can be retrieved with the len() built-in, so this function is completely unnecessary).

You could get shorter code if you want: 

def count(L):
    return count(L[:-1])+1 if L else 0

But you still need to change python's recursion limit. 

import sys; sys.setrecursionlimit(100000)

However, we should note that in most cases, "if else" statements take longer to process than "try except". Hence, "try except" is going to be a better (if you are after performance). Of course, that's weird talking about performance because recursion typically doesn't perform very well, due to how python manage's namespaces and such. Recursion is typically frowned upon, unnecessary, and slow. So, trying to optimize recursion performance is a littler strange.

A last point to note. You mention the temp=arr[i] taking up memory. Yes, possibly a few bytes. Of course, any calculation you do to determine if arr has an element at i, is going to take a few bytes in memory even simply running "arr[i]" without assignment. In addition, those bytes are freed the second the temp variable falls out of scope, gets re-used, or the function exits. Hence, unless you are planning on launching 10,000,000,000 sub-processes, rest assure there is no performance degradation in using a temp variable like that.

Upvotes: 1

maede rayati
maede rayati

Reputation: 786

You can use pop() to do it.

def count_r(l):
    if l==[]:
        return 0
    else:
        l.pop()
        return count_r(l)+1

Upvotes: 1

HackLab
HackLab

Reputation: 539

you are prob looking for something like this

def count_rec(arr):
    if arr == []:
        return 0
    return count_rec(arr[1:]) + 1

Upvotes: 1

Related Questions