CODEWITHSUNDEEP
pythonalgorithmrecursion
user2969278
user2969278

Reputation: 29

python - Not sure if recursive or not

def func_palindrome(stri):
    if len(stri) == 0 or 1:
        return True
    if stri[0] != stri[-1]:
        return False
    return func_palindrome(stri[1:-1])

I'm not sure if this function, that checks if the string is a palindrome can be considered as a recursive code or not. That becuase I can simply change the last return value from return func_palindrome(str[1:-1]) to True and nothing will change

Upvotes: 0

Views: 117

Answers (3)

dstromberg
dstromberg

Reputation: 7187

You don't need to do this recursively, but you can, particularly if you don't mind a lot of extra space and poor performance for long strings.

Here are two nonrecursive ways:

#!/usr/bin/python3

def is_palindrome1(string1):
    string2_list = list(string1)
    string2_list.reverse()
    string2 = ''.join(string2_list)
    return string1 == string2

def is_palindrome2(string):
    len_string = len(string)
    for index in range(len_string // 2):
        character1 = string[index:index+1]
        character2 = string[len_string-index-1:len_string-index]
        if character1 == character2:
            # This character is good
            pass
        else:
            return False
    # all characters matched
    return True

for string in [ '393', '339', 'aibohphobia', 'aibobphobia' ]:
    assert is_palindrome1(string) == is_palindrome2(string)
    print(is_palindrome1(string))
    print(is_palindrome2(string))

Upvotes: 1

abarnert
abarnert

Reputation: 366213

Any function that calls itself is technically a recursive function.

Any function that checks its arguments for a "base case", and otherwise calls itself with a "smaller" version of its arguments, is a usefully recursive function.

Of course a recursive function can still be broken, or even pointless. For example, consider this function:

def recursive_length(a):
    if not a:
        return 0
    return 0 + recursive_length(a[1:])

My stupid bug in the last line doesn't mean this is not a recursive function. I'm recursively summing up N copies of the number 0, instead of N copies of the number 1, so I could have done the same thing by just writing return 0. But that's just because the sum of N copies of 0 is always 0, not because my function fails to be recursive.

So, what if there were a problem in the base case?

def recursive_length(a):
    if a is not None:
        return 0
    return 1 + recursive_length(a[1:])

Now, it never actually recurses… but it's still a recursive function. It's just a recursive function with a bug in the base case.

Upvotes: 1

karthikr
karthikr

Reputation: 99680

Your issue is here:

if len(str) == 0 or 1 :

should be

if len(str) == 0 or len(str) == 1:

By just doing if len(str) == 0 or 1 it is evaluating to True always as it is interpreted as (len(str) == 0) or 1

Also, I would rename str to something else, as str is a builtin type

Upvotes: 7

Related Questions