Opened 10 years ago

Closed 10 years ago

# Maximum recursion depth exceeded in the computation of return words

Reported by: Owned by: slabbe slabbe major sage-4.7 combinatorics jleroy sage-4.7.alpha2 Sébastien Labbé Julien Leroy N/A

### Description

```---------- Forwarded message ----------
From: Julien Leroy
Date: 2011/1/19
To: Sébastien Labbé

Voici quelques exemples des comportements bizarres que j'ai pu observer.

A bientôt,
Julien

sage: TM = words.ThueMorseWord('01')[:1000]
sage: TM
word: 0110100110010110100101100110100110010110...
sage: TM.return_words(Word('0'))
set([word: 0, word: 01, word: 011])

sage: TM = words.ThueMorseWord('01')[:10000]
sage: TM
word: 0110100110010110100101100110100110010110...
sage: TM.return_words(Word('0'))
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded while calling a Python object

sage: f = WordMorphism('a->ab,b->ba')
sage: tm = f.fixed_point('a')[:1000]
sage: tm
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: tm.return_words(Word('a'))
set([word: a, word: ab, word: abb])

sage: tm = f.fixed_point('a')[:10000]
sage: tm
word: abbabaabbaababbabaababbaabbabaabbaababba...
sage: tm.return_words(Word('a'))
Traceback (most recent call last):
...
IndexError: string index out of range
```

### comment:1 follow-up: ↓ 2 Changed 10 years ago by slabbe

• Status changed from new to needs_review

This should fix the problem. Needs review.

### comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 10 years ago by jleroy

This should fix the problem. Needs review.

Hi Seb,

All test passed and it seems to fix the problem, indeed. However I have a few questions that probably come from the fact that I still don't know much about sage development.

1. In most of the things that you added or modified in that patch, the functions do not contain any tests. Is there any reason for that?
1. You added some "@cached_method". If I remember well, the cached_method means that what follows does not appear in the list of functions given by the "tab completion", doesn't it? However, those functions (for instance the "good_suffix_table" at line 816) do appear in that list. Am I wrong about the cached_method?

Julien

### comment:3 in reply to: ↑ 2 Changed 10 years ago by slabbe

1. In most of the things that you added or modified in that patch, the functions do not contain any tests. Is there any reason for that?

That's because tests were already there. In many cases, I just changed the code and kept the documentation and doctests as is.

That being said, it is true that I didn't add any tests for the problem mentionned in this ticket. I am going to add one right now and re-upload the patch.

1. You added some "@cached_method". If I remember well, the cached_method means that what follows does not appear in the list of functions given by the "tab completion", doesn't it? However, those functions (for instance the "good_suffix_table" at line 816) do appear in that list. Am I wrong about the cached_method?

Cached method do and should appear in the tab completion list. A cached method means that it remembers its result instead of computing it everytime. En français, on parle de mémoization:

In our case, the `good_suffix_table` is consulted everytime we search for a factor. So for searching the return words of a factor, it might be a good speedup to cache (mémoiser) the good suffix table.

### Changed 10 years ago by slabbe

Applies over sage-4.6.1

### comment:4 follow-up: ↓ 5 Changed 10 years ago by slabbe

I just refreshed the patch. Needs review! If you have any question Julien, just ask me!

### comment:5 in reply to: ↑ 4 Changed 10 years ago by jleroy

• Status changed from needs_review to positive_review

I just refreshed the patch. Needs review! If you have any question Julien, just ask me!

Great! All test passed and the problem is fixed. Nice job and thank you for your explicatiosn!

### comment:6 Changed 10 years ago by jdemeyer

• Authors set to Sébastien Labbé
• Milestone changed from sage-4.6.2 to sage-4.7
• Reviewers set to Julien Leroy

### comment:7 Changed 10 years ago by jdemeyer

• Merged in set to sage-4.7.alpha2
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.