再帰処理 エラーも結果も出ないので原因が分からない

Question

###まとめ
動くか動かないかの切り分けは完全には出来ていませんが特にPythonのVer差でもOS差でも無いような気がします。

GitHub 修正後のコードまとめ

動かなかった環境は以下のとおりです。
全てNG
・OS:Windows10 Home 64bit
・Python:3.6.6 , 3.7.0
・IDE:Eclipse4.8 , Jupyter Notebook
・コマンドライン

その他コメントより
NG
・3.4.3 on Windows8.1/64bit

OK
・3.7.0

@hayataka2049さんの回答より
Python: What is the hard recursion limit for Linux, Mac and Windows? - Stack Overflow
Windows版Pythonの再帰呼び出し制限 - kusano_kの日記

sys.setrecursionlimit(1024*1024)

で再帰呼び出しの深さ制限を変更できるけど、Pythonのスタックサイズが足りないらしく、Pythonが不正終了する。Windowsの場合、新しく作成されるスタックのサイズを
thread.stack_size(12810241024)
で変更できる。

@LouiS0616さん回答より
@functools.lru_cache(maxsize=128, typed=False)

関数をメモ化用の呼び出し可能オブジェクトでラップし、最近の呼び出し最大 maxsize 回まで保存するするデコレータです。高価な関数や I/O に束縛されている関数を定期的に同じ引数で呼び出すときに、時間を節約できます。

　

フィボナッチ数列絡みの問題を再帰で実装する際は、

functools.lru_cache でメモ化するとトラブルが少ないです。

どちらのコードも試してみて動作確認出来ました。
個人的にはimportと@デコレータ追記だけなのでこちらが実用的かとは思います。

追記補足：
但し質問時の元のコードのままで@デコレータ追記だけでは動きませんでした。
@LouiS0616さん回答のように関数を分割すると動きました。
GitHub 修正後のコード qa151136_ok2.py

from functools import lru_cache
# @lru_cache(maxsize=None)
@lru_cache(maxsize=8)
def fibo(n):

Pythonで再帰階層が深くなる場合には気をつけるという教訓にもなりました。
回答やコメントなどでの情報提供ありがとうございました。

###知りたいこと
エラーも結果も出力されない原因が知りたいです。
原因が分かる方いらっしゃればご教示お願いします。

###起きている現象
Problem 25 : 1000-digit Fibonacci number
上記問題を解くのに下記プログラムでN=1000を入力すると正解が出力されるはずなのですが、
関数の再帰処理を使い入力値をN=823以上にすると結果もエラーも表示されずに終了してしまいます。

###実行環境
Windows10
Python3.7.0

import sys
import math
# 再帰回数の上限
# sys.setrecursionlimit(2100000000)
sys.setrecursionlimit(10000)

def fibo2(n_1, n_2, count):
    n = n_1 + n_2
    count += 1
    if n >= target:
        return count
    return fibo2(n, n_1, count)

# N = 1000で問題を解きたいのに
# N = 823以上になると結果が表示されない
# N = 823
N = 822
target = 10 ** (N-1)
print(fibo2(1, 1, 2))

# 検算
# N = 3
# 12

##試したこと
whileループで書き換えると結果が出るので桁数の問題では無いことは確認済みです。

def fibo1(target):
    a, b = 1, 1
    cnt = 2
    target -= 1
    while b < 10 ** (target):
        cnt += 1
        a, b = b, a + b
    return cnt

target = 1000
print(fibo1(target))
# 出力結果
# 4782

最初は再帰回数の上限でエラーが出たので調べたら上限設定を変更可能と知ったので変更済みです。

import sys
# 再帰回数の上限
# sys.setrecursionlimit(2100000000)
sys.setrecursionlimit(10000)

Comments

[LouiS0616]

実行環境は何ですか？

[opyon]

実行環境とはOSのことでしょうか？OSでしたらWindows10-64bitで、Python3でしたら3.7.0です。
質問内容にも追記編集しました。

[opyon]

Jupyter Notebookでも実行出来ないのとクラシュしたとエラーが出たので再起動しようとしたら、windows更新があるようなので実行して再起動してみます。

Answer 1

手元環境のwindowsで、823回では問題ありませんでしたが、850回程度まで増やしてコマンドプロンプトから実行すると強制終了（「python.exeは動作を停止しました」ダイアログが出てそのまま終了）になりました。

あまり詳しくありませんが、この辺の話だと思います。

Python: What is the hard recursion limit for Linux, Mac and Windows? - Stack Overflow

Windows版Pythonの再帰呼び出し制限 - kusano_kの日記

sys.setrecursionlimit()はインタプリタ側の設定を変更するだけで、実際にスタックとして使える領域の容量には別途制限がある・・・ということらしいです。ややこしいですが。

以下のコードに書き換えて実行できることを確認しました。

# coding: UTF-8
import sys
import threading
sys.setrecursionlimit(2100000000)
threading.stack_size(128*1024*1024)  # 追加

def fibo2(n_1, n_2, count):
    n = n_1 + n_2
    count += 1
    if n >= target:
        return count
    return fibo2(n, n_1, count)

def f():
    global target  # 汚いけどとりあえず
    N = 1000
    target = 10 ** (N-1)
    print(fibo2(1, 1, 2))

threading.Thread(target=f).start()

Comments

[opyon]

ありがとうございます。
今コピペして動作確認出来ました。
もう少し調べてみます。

[opyon]

差し支えなければ後学のためにどのような検索などしたのか教えて頂けると助かります。

[hayataka2049]

python recursion windowsとかでググってたら上のリンクのスタックオーバーフローを見つけて、あとはそこからキーワードを拾って芋づる式に

[opyon]

なるほど、ありがとうございます。
日本語で再帰で検索していました。
recursionが再帰という意味も今知りました。
最初から英語で調べることが大事なのですね。

Answer 2

フィボナッチ数列絡みの問題を再帰で実装する際は、
functools.lru_cache でメモ化するとトラブルが少ないです。

from functools import lru_cache
from itertools import count


@lru_cache(max_size=8)
def fibo(n):
    if n in (1, 2):
        return 1

    return fibo(n-1) + fibo(n-2)


def fibo2(target):
    for i in count(start=3):
        if fibo(i) >= target:
            return i


N = 1000
target = 10 ** (N-1)
print(fibo2(target))

今回失敗した原因については、hayataka2049さんのご指摘のとおりかと思います。

Comments

[opyon]

ありがとうございます。
最初にmaxsize=8とするとエラーが出て動かず8,16,32と増やしても動かず、Noneにして動きました。
その後再度8に戻すと動きました。再現性が無いのですが一応報告しておきます^^;
# @lru_cache(maxsize=None)
@lru_cache(maxsize=8)

[opyon]

コードとしてはこちらの方がアノテーション追加だけでシンプルなので実用的ですが、
情報提供面で@hayataka2049さんにBAを送りたいと思います。ご了承ください。

[LouiS0616]

・BAについて
私もそれが適当かと思います。
私の回答は解決法を示しただけで、原因には言及していませんので。

・アノテーション
アノテーションはJavaの用語ですね。
Pythonではデコレータと呼び、わりあい機能も単純です。というか、ただのシンタックスシュガーです。

[opyon]

失礼しました^^;
デコレータに訂正しておきます。

Answer 3

WindowsでもLinuxでも問題なくN=1000が実行できます。
特殊な実行環境なのでは？ウェブ上とか？

Comments

[opyon]

ありがとうございます。
環境を変えて試してみます。

[otn]

Windowsでも環境により違うみたいですね。
Python 3.6.2 on Windows7/64bit
です。

[opyon]

3.6.6でも動かず、Jupyter Notebookでも動かず・・・
後ほど試したことを質問内容に書いておきます。

[otn]

動かない原因としては、スタックの不足でしょうが、エラーが出ないというので、ウェブ上のプログラム実行環境なのかなと思っておりました。
出力無しで正常終了したように見えると言う事ですよね？
コマンドプロンプトから直接実行した場合もですか？

[hayataka2049]

@otnさん, opyonさん
私はPython 3.4.3 on Windows8.1/64bitでした。公式配布の.exeのインストーラで入れたはず
（3.4.3は笑ってください、数年前インストールして最近は放置している常用していない環境です）

ビルドによって違うとかかなぁ・・・

[LouiS0616]

Python 3.6.5 Anaconda Windows10/64bit でも無言でヘタりました。

[otn]

たった今、公式サイトで3.7.0に上げてみましたが、N=1000で4782と出ますね。
何が違うんだろう？

[opyon]

何でしょうね・・・
@otnさんの環境がハイスペックとか？

[otn]

再度聞きますが、
コマンドプロンプトから直接実行した場合もですか？

[opyon]

@otnさんへ
すみません、コメント見落としていました。
コマンドプロンプトから直接実行したこと無いのですが・・・
すぐには出来ないので時間掛かると思いますが調べて試してみます。

[opyon]

コマンドプロンプトでも無言終了でした。
質問のまとめに画像リンク貼りました。