profondeur de récursivité maximale dépassée en comparaison?

Question

Commencé à apprendre python, c'est le sous-ensemble de la somme maximale que j'ai essayé. Finissant avec "profondeur de récursivité maximale dépassée en comparaison". Mon algorithme me semble ok. S'il vous plaît aidez-moi si je fais quelque chose de mal.

import sys 
import math 
def maxtuple(lss,rss): 
    if lss[2] > rss[2]: 
     return lss 
    else: 
     return rss 
def crosssubarray(A, start, mid, end): 
    ls=rs=-sys.maxsize 
    maxleft=0 
    maxright=0 
    sum = 0; 
    for i in reversed(range(start, mid)): 
     sum = sum + A[i] 
     print(i) 
     if sum > ls: 
      ls = sum 
      maxleft = i 
    sum = 0 
    for i in range(mid+1, end): 
     sum = sum+ A[i] 
     if sum > rs: 
      rs = sum 
      maxright = i 
    return (maxleft, maxright, ls+rs) 

def maxsubarray(A,start,end): 
    if start == end: 
     return (start,end,A[start]) 
    else: 
     mid = (start+end)/2 
     lss = maxsubarray(A, start, mid) 
     rss = maxsubarray(A, mid+1, end) 
     css = crosssubarray(A, start, mid, end) 
     maxsub = maxtuple(lss,rss) 
     maxall = maxtuple(maxsub, css) 
     return maxall 

A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] 
print(maxsubarray(A,0,15)) 

Answer 1

Votre problème réside dans cette fonction:

def maxsubarray(A,start,end): 
    if start == end: 
     return (start,end,A[start]) 
    else: 
     mid = (start+end)/2 
     lss = maxsubarray(A, start, mid) 
     rss = maxsubarray(A, mid+1, end) 
     css = crosssubarray(A, start, mid, end) 
     maxsub = maxtuple(lss,rss) 
     maxall = maxtuple(maxsub, css) 
     return maxall 

Pour être précis, les 5 premières lignes. La raison de "travailler" (ne sait pas votre résultat attendu) dans python 2.x est parce que / est pour la division de plancher, alors que dans python 3.x / est pour la division de point de flottement. Et grâce à l'erreur d'arrondi virgule flottante, start est probablement probablement jamais égal à end.

---

Si la division étage entier est ce que vous allez pour, vous pouvez remplacer le / à un //.

Ce faisant, l'erreur disparaît et retourne (8, 10, 32)

Answer 2

Vous pouvez augmenter la profondeur de la pile autorisée - avec cela, les appels récursifs plus profond sera possible, comme ceci:

import sys 
sys.setrecursionlimit(10000) # 10000 is an example, try with different values 

... Mais Je vous conseille de d'abord essayer d'optimiser votre code, par exemple en utilisant l'itération au lieu de la récursivité.