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

Question

我正在尝试实现本课程在python2.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

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

如果您能指出我在实施过程中可能犯的错误，我将不胜感激

Answer 1

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

Answer 2

更改递归限制是危险的，因为通常当您超过递归限制时，这是因为您的程序包含错误或糟糕的设计决策。递归总是可以用相同或更低内存开销的迭代来代替

除非你的算法要求你这样做，因为你知道在某个时候你会收到一个结果，你可以改变最大递归深度每次你调用你的函数，但我还是不建议，因为你的程序超过1500递归调用时，你设置它，这是非常过分

# Karatsuba multiplication implementation in python

import numpy as np
import sys

def algo_recurs(val1, val2):
    sys.setrecursionlimit(sys.getrecursionlimit() + 1)  # Changes the recursion limit every time
    n = len(str(val1))
    #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

    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
        return(finalResult)

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