时间戳

首页 > 解决方案 > 在 Python 中计算字符串长度时出现“递归深度超出错误”

python - 在 Python 中计算字符串长度时出现“递归深度超出错误”

问题描述

我正在尝试在 python 2.7 中实现课程中提到的 Karatsuba 算法。这是我目前得到的代码：

# Karatsuba multiplication implementation in python

import numpy as np
import sys

# x = 10^(n/2)*a + b and y = 10^(n/2)*c + d
# x.y = 10^n*(ac) + 10^(n/2)*(ad + bc) + bd
# now recursively compute ac, ad, bc and bd

sys.setrecursionlimit(15000)

def algo_recurs(val1, val2):
  # Assuming that the length of both the multiplier and multiplicand is 
    same
  # Currently employing numbers which are of length 2^n
  n = len(str(val1))            # n = 4
  print(n)
  divVal    = 10**(n/2)
  a = val1 / divVal         # a = 12
  b = val1 % divVal         # b = 34
  c = val2 / divVal         # c = 43
  d = val2 % divVal         # d = 21
  # let the example case be 1234 * 4321

  if(len(str(val1)) == 2):
    prob1 = a * c
    prob2 = b * d
    prob3 = (a+b)*(c+d) - prob1 - prob2
    finalResult = prob1*(divVal*divVal)+prob3*divVal+prob2
    return(finalResult)
  else:
    prob1 = algo_recurs(a,c)
    prob2 = algo_recurs(b,d)
    prob3 = algo_recurs((a+b),(c+d)) - prob1 -prob2
    finalResult = prob1*(divVal*divVal)+prob3*divVal+prob2
    #print(finalResult)
    return(finalResult)
#Enter the inputs

multiplicand    = input("Enter the multiplicand:")
multiplier      = input("Enter the multiplier:")
output = algo_recurs(multiplicand, multiplier)  
print(output)

上面的代码适用于长度为 4 或更少的数字。但是当我超越这一点时，它会引发以下错误：

File "Karatsuba.py", line 31, in algo_recurs
  prob1 = algo_recurs(a,c)
File "Karatsuba.py", line 31, in algo_recurs
  prob1 = algo_recurs(a,c)
File "Karatsuba.py", line 31, in algo_recurs
  prob1 = algo_recurs(a,c)
File "Karatsuba.py", line 15, in algo_recurs
  n = len(str(val1))            # n = 4
RuntimeError: maximum recursion depth exceeded while getting the str of an object

我也增加了递归限制，认为这可能是问题所在。但这也没有解决它。

如果您能指出我在实施中可能做错了什么，我将不胜感激。

标签： pythonalgorithm

解决方案

无论您将递归限制设置多高，您的算法都不会终止。这是因为参数 a 和 c 在达到个位数后将始终保持不变val1，因为 thenn是 1，10**(n/2)也是 1。

推荐阅读