Tag: recursion

Recursion Function Isn't Working

Okay, so I’m trying to make a recursive function that returns True if the function is a palindrome, and False otherwise. However, it doesn’t go to the very end, and randomly stops.

Code:

def is_palindrome(word):

    if len(word) == 1 or len(word) == 0:
        return True
    else:
        lst = len(word) - 1
        if word[0] == word[lst]:
            print(len(word), " --> ", word)
            print(word[0], " # ", word[lst])
            is_palindrome(word[0+1:lst])
        else: 
            return False

For the life of me, I can’t figure out why. Here’s a sample output:

7  -->  racecar
r  #  r
5  -->  aceca
a  #  a
3  -->  cec
c  #  c

^ It stops right here. Why doesn't it continue and return True when length = 1?

Solution:

You need to return your call to the recursive function:

def is_palindrome(word):

    if len(word) == 1 or len(word) == 0:
        return True
    else:
        lst = len(word) - 1
        if word[0] == word[lst]:
            print(len(word), " --> ", word)
            print(word[0], " # ", word[lst])
            return is_palindrome(word[0+1:lst])     # change here
        else: 
            return False

The reason you code appears to stop at the final step of recursion is because you never actually return a value in that case. In some programming languages, such as C or maybe Java, such code would not even compile. Python appears to tolerate it, though it results in your current behavior.

Recursive and random grouping a list

I’m trying to write a function which creates dichotomously grouped list, f. ex. if my input is as following:

[a, b, c, d, e, f, g, h]

I want to choose random integer which will split it into smaller sublists again and again recursively until the sublists’ length is maximum two, like:

[[a, [b, c]], [d, [[e, f], [g, h]]]]

This is what I’ve got so far but still gives me
TypeError(list indices must be integers or slices, not list):

def split_list(l):
    if l.__len__() > 2:
        pivot = np.random.random_integers(0, l.__len__() - 1)
        print(pivot, l)
        l = [RandomTree.split_list(l[:pivot])][RandomTree.split_list(l[pivot:])]
    return l

I got stuck and I would be very thankful for any advice.

Solution:

Here’s a solution that will not make one-element lists, as per your example:

import random

def splitlist(l, minlen=2):
    if len(l) <= minlen:  # if the list is 2 or smaller,
        return l if len(l) > 1 else l[0]  # return the list, or its only element
    x = random.randint(1, len(l)-1)  # choose a random split
    return [splitlist(l[:x], minlen), splitlist(l[x:], minlen)]

Usage example:

>>> splitlist(list(range(8)))
[[0, [1, [2, [3, 4]]]], [[5, 6], 7]]

Python recursion is very slow

I am a novice at python, but was surprised at how slow this recursive call took to execute:

def daH(m:int):
    if m == 1:
        return int(1)
    else:
        if m <= .5 * (daH(m-1) * (daH(m-1) +1)):
            return int(daH(m-1))
        else:
            return int(daH(m-1) + 1)

print(daH(10)) # prints 4
print(daH(11)) # prints 5
print(daH(15)) # prints 5    
print(daH(16)) # prints 6

print(daH(106)) # prints ??? (gave up waiting)

I ran it on IDLE, python 3.6. I added the INT stuff but it did not help. I had no problems running the standard factorial recursion and printing factorial(106).

Can this attempt at recursion be salvaged?

Solution:

You are computing daH(m-1) 3 times, making the algorithm slower than necessary. Instead, calculate it just once and bind the result to a local variable. (Also, not necessary to cast to int)

def daH(m:int):
    if m == 1:
        return 1
    else:
        r = daH(m-1)
        if m <= .5 * r * (r + 1):
            return r
        else:
            return r + 1

Calling the function three times instead of once may not seem like much, but remember that those calls will stack exponentially! You call it three times, and each of those again call it three times, and so on. This results in a complexity of O(3m), which even for m=15 results in about 15 million recursive calls, as opposed to the 15 that are actually necessary.