Is it possible to convert the following loop:
c = 0
for a in find:
c += 1
return c
Where find is a list like [a,b,c,d] to a function that uses recursion without using external libraries?
3 Answers
def count(ls):
if not ls: # empty
return 0
return count(ls[1:]) + 1
Use it like this:
>>> find = [a, b, c, d]
>>> count(find)
4
2 Comments
RoadRunner
You should change to
return count(ls[1:]) + 1, otherwise you'll get a RuntimeError: maximum recursion depth exceeded error. I didn't DV btw.
L3viathan
Yep, sorry, oversight.
I managed to do so by defining the following function:
def ric(find, n, c):
if n < len(find):
if find[n] in find:
c += 1
n += 1
return ric(find, n, c)
else:
return c
and calling it with ric(find, 0, 0)
Comments
Something as simple as this would work:
def to_rec(lst):
# base case, when list is empty
if not lst:
return 0
# recursive case
return 1 + to_rec(lst[1:])
Base case: If the list has no elements, return 0.
Recursive case: Otherwise return 1 + the length of the list, minus one element, which is why we use [1:] here, to disregard the head of the list.
You could also explicitly set an accumulator with a helper function. If you've ever used a functional programming language, such as Haskell or Prolog, this technique is quite popular. Here is what it could look like:
# main function
def to_rec(lst):
# calls helper function with starting accumulator of 0
return accum(lst, 0)
def accum(lst, acc):
# returns accumulator instead
if not lst:
return acc
# increments accumulator, and looks at the tail of the list
return accum(lst[1:], acc + 1)
Both work as follows:
>>> print(to_rec(['a', 'b', 'c', 'd']))
4
>>> print(to_rec([]))
0
>>> print(to_rec(['a']))
1
ato be in the list? Or justsome elementin list?