3

the task I am doing is:

Given an array of ints, compute recursively the number of times that the value 11 appears in the array. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array.

I need to do this recursively. I'm rather new at this, but I technically made it work. I have the following:

def array11(arr, index, cnt=0, num=0):
    if(cnt==len(arr)-index):
        print("yay!!! number 11 appears %d times"%num)
        return
    elif(arr[index:][cnt]==11): 
        num+=1
        cnt+=1
        array11(arr,index,cnt,num)
    else: 
        cnt+=1
        array11(arr,index,cnt,num)

but I feel I did it a cheap way for some reason by adding the "cnt" and "num" parameters with default values. I just didn't know how to go through the "arr" array without a counter!!

So this this something acceptable? Would you have done it the same way?

thanks in advance

2
  • This is almost certainly too opinion based, and since it's working code, perhaps a better fit for Code Review. That said, arrays aren't a recursive datatype (as opposed to singly linked lists), so this seems like a pretty natural solution given the datatype. Plus, it's tail recursive, so it could be compiled down to a loop, which is good. Jul 11, 2014 at 17:05
  • +1 for making an attempt before asking. I edited your title to reflect the problem at hand.
    – timgeb
    Jul 11, 2014 at 17:10

3 Answers 3

5

You normally return the total count:

def array11(arr, index):
    if index == len(arr):
        return 0
    return (arr[index] == 11) + array11(arr, index + 1)

I am using a little Python trick here where bool is a subclass of int and True is equal to 1. As such, adding up booleans (or booleans and integers) results in the boolean values to be interpreted as integer numbers instead.

You'd use print then on whatever the outermost call to array11() returned.

10
  • but OP's was tail-recursive :| Jul 11, 2014 at 17:07
  • 2
    That addition doesn't chain? array11([11,2,3], 0) would produce 1 + array11([11,2,3], 1) -> 1 + 0 + array11([11,2,3], 2) -> 1 + 0 + 0 + array11([11,2,3], 3) -> 1 + 0 + 0 + 0 = 1 right ? Jul 11, 2014 at 17:08
  • 2
    +1 but you might want to throw parenthesis around your boolean expression there to make it a little more clear what you're doing
    – scohe001
    Jul 11, 2014 at 17:08
  • 1
    @Josh: done, plus explanation added as to how arr[index] == 11 is summable.
    – Martijn Pieters
    Jul 11, 2014 at 17:09
  • @HunterMcMillen: Ick, I need my tea still. Not that it matters, as Python doesn't optimise tail recursion.
    – Martijn Pieters
    Jul 11, 2014 at 17:12
1

This is perfectly acceptable, albeit not the cleanest way to perform tail recursion. What you are doing is called using an accumulator to keep track of your count, which allows you to have tail recursion (the more efficient type of recursion).

However, as BlackVegetable points out, Python doesn't allow you to reap the benefits of tail recursion, but it's definitely noteworthy to understand the difference between using an accumulator vs a top down approach as in Martijn Pieter's answer.

3
  • Using an accumulator isn't particularly unclean; what might be cleaner is to make calls like array11(arr,index,cnt+1,num+1) rather than modifying cnt and num and then making the calls. Jul 11, 2014 at 17:07
  • @JoshuaTaylor sure, meant more the code itself. He could use an accumulator differently. And now your comment on the OP's question does ring true :)
    – C.B.
    Jul 11, 2014 at 17:08
  • 3
    Tail recursive calls are not optimized in Python, IIRC. Jul 11, 2014 at 17:10
0

In Python 3 it can be as concise as this:

arr = [11, 0, 4, 7, 2, 11, 6, 11, 12]

def count11(arr):
    if not arr:
        return 0
    first, *rest = arr
    return (1 if first == 11 else 0) + count11(rest)

count11(arr) # 3

The list slicing may not be very efficient, but since we're talking about recursion in Python, in assume performance is not a factor.

Not the answer you're looking for? Browse other questions tagged or ask your own question.