質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

9234閲覧

pythonの再帰の深さの限界

退会済みユーザー

退会済みユーザー

総合スコア0

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2016/08/30 03:14

###前提・実現したいこと
pythonで再帰関数を使用したいのですが,再帰の深さに上限があって困っています。

###発生している問題・エラーメッセージ
16GBのメモリをのせているのですが,再帰の深さが25000を超えるとsegmentation faultが発生し,プログラムが落ちてしまいます。

###該当のソースコード

import sys sys.setrecursionlimit(500000) def func(i): print i func(i+1) func(1)

###試したこと
実行中の使用メモリを観察していましたが,ほとんどメモリは使用されていませんでした。

###補足情報(言語/FW/ツール等のバージョンなど)
環境はubuntu 14.04, Anaconda2です。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yohhoy

2016/08/30 03:34 編集

あなたのプログラムでは、*本当に*25000回もの再帰呼び出しが必要なのでしょうか???末尾再帰呼出最適化をもたないPythonでは、数千を超える再帰呼び出しをすること自体、プログラム設計上の致命的な誤りを示しています。
退会済みユーザー

退会済みユーザー

2016/08/30 03:44

ご意見有難うございます。行いたい処理は,再帰を用いた画像の塗りつぶしアルゴリズムの実装です。本来はC言語で実装するべきアルゴリズムだとは思うのですが,プログラム全体をPythonで書いているため塗りつぶしのアルゴリズムもPythonで実装しようとしました。
yohhoy

2016/08/30 03:46

C言語でも事情は同じです(どんなに特殊なプログラムでも再帰呼び出しの上限は数千程度)。再帰回数をある程度抑えるように、アルゴリズム自体を書き換える必要があると思います。
snowfaller

2016/08/30 05:03

「環境はubuntu 14.04」とのことですが、64ビット環境(PAEではない)でよろしかったでしょうか? 不明な場合「uname -a」の結果を追記いただけますでしょうか?
guest

回答1

0

ベストアンサー

再帰呼び出しするたびに、スタック上に新たなメモリ領域が作られます。その総量がPythonのプロセスに割り当てられたメモリ量を超えれば、segmentation faultが発生します。

プロセスに割り当てるメモリ量を増やせば再帰呼び出し回数の上限は上がりますが、質問者の実行したい再帰呼び出し回数(50万回?)が可能になるかどうかは、実際にやってみて確認するしかないと思います。

再帰呼び出しをつかったコードがスタック量の制限で実行できなくなることは、よくある事です。
そうした場合には、再帰呼び出しのコードをループを用いたコードに書き換える事で解決を図るのが普通です。

投稿2016/08/30 04:09

coco_bauer

総合スコア6915

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/30 07:17

皆様,ありがとうございました。最終的に,ループを用いたコードに書き換えることで対応しました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問