Converting a iteration into recursion

Question

I'm trying to learn python recursion, and trying to code the following question with just recursion: Given a string and a character, return the number of times the character is shown in the string. Ex: 'p', 'Apple' should return 2

Here is my code below:

def count(char,text):
    total=0
    if char==text[0]:
        total+=1
        if len(text)==1:
            print( total)
        else:
            return count(char,text[1:])
    else:
        return count(char,text[1:])
   

I think what is really messing me up is the variable total always being reset to 0 on each recursion. In addition, I'm not totally confident in my base case. How can I fix this?

Answer 1

Here's one way you could do it, though it's a bit memory inefficient because it has to create a new string for every recursive call.

def count(char, text):
    if not text:
        return 0
    return (1 if text[0] == char else 0) + count(char, text[1:])

You could improve the memory efficiency a bit by passing an index along so that it can reuse the same string and doesn't have to create a new one each time.

def count(char, text, i=0)
    if i >= len(text):
        return 0
    return (1 if text[i] == char else 0) + count(char, text, i + 1)

To explain some of the syntax to those that may not be familiar with it, this is the python ternary operator

1 if text[i] == char else 0

Functionally, its the same as

if text[i] == char:
    return 1
else:
    return 0

It's just shorter and still easy to read.