maximum recursion depth exceeded in python class, project Euler #4

Question

I was working on a solution for Project Euler's Question #4:

"Find the largest palindrome made from the product of two 3-digit numbers."

I could just write a basic script and loop, but I tend to write things within classes.

I've been out of python for a while, so I'm using these exercises to stay familiar with the language.

While looping through the factors to figure out the answer, I receive this error:

File "p4.py", line 35, in is_palindrome
n = str(p)
RuntimeError: maximum recursion depth exceeded while getting the str of an object

I'm guessing it's the way I formatted my recursive method, but I can't figure out how to fix it.

Could someone explain to me what I'm doing wrong in terms of structuring my recursive method?

The code:

import math

class PalindromeCalculator:

  def __init__(self, min_factor=100, max_factor=999):
    self.stable_factor = max_factor
    self.variable_factor = max_factor

  def find_max_palindrome(self):
    return self.check_next_product()

  def check_next_product(self):
    product = self.stable_factor * self.variable_factor;
    if self.is_palindrome(product):
      print("We found a palindrome! %s" % product)
      return str(product)
    else:
      # Reduce one of the factors by 1
      if self.variable_factor == 100:
        self.variable_factor = 999
        self.stable_factor -= 1
      else:
        self.variable_factor -= 1

      self.check_next_product()

  def is_palindrome(self, p):
    # To check palindrom, pop and shift numbers off each side and check if  they're equal
    n = str(p)
    length = len(n)

    if length % 2 == 0:
      iterations = length / 2
    else:
      iterations = (length - 1) / 2

    for i in range(0, iterations):
      first_char = n[i:i+1]
      last_char = n[-(i+1)]

      if first_char != last_char:
        return False

    return True

And to run the function:

start = time.time()
calculator = PalindromeCalculator();
M = calculator.find_max_palindrome()
elapsed = (time.time() - start)

print "My way: %s found in %s seconds" % (M, elapsed)

Just a minor typo, but very hard to find: You are never using the `min_factor` parameter in your constructor. — Ocaso Protal, Mar 24 '16 at 13:55

score 0 · Answer 1 · answered Mar 24 '16 at 13:54

This is similar to a StackOverflowError in Java. Because check_next_product is calling itself so much there are too many nested function calls and Python has given up on keeping track of them all. You can increase the recursion limit but the fact that the recursion is so deep shows that you'd be much better off writing an iterative solution. Recursion isn't really suited to this problem.

score 0 · Answer 2 · edited May 23 '17 at 12:31

0

Check this: maximum recursion depth exceeded while calling a Python object

anyway, it is quite simple to write an iterative algorithm for it so there is no need to use the recursion.

edited May 23 '17 at 12:31

Community

1
1

answered Mar 24 '16 at 15:33

Alex L

1,069
2
18
33

maximum recursion depth exceeded in python class, project Euler #4

2 Answers2