- ベストアンサー
再帰関数のインライン展開
再帰関数のインライン展開は出来るのでしょうか? もし、出来るようならアセンブラではどのように表現されているんですか? C以外の言語でも、再帰関数のインライン展開が出来るプログラム言語があれば教えてください。
- C・C++・C#
- 回答数7
- ありがとう数6
- みんなの回答 (7)
- 専門家の回答
質問者が選んだベストアンサー
> というのは、最適化をせずに、明示的にインライン指定をしなくても自動でインライン展開(可能な限り)をしてくれるということですね。 > 逆にCでは最適化をするかインライン指定をしないとインライン展開(可能な限り)をしてくれないということですか? ちょっと違います。 確かに、明示的にinlineを付けなくても、最適化でインライン展開されることはありますが、ここで取り上げているのはinlineというキーワードの意味についてです。 C++ではinlineを付けた関数はインライン展開を目指すのに対して、Cではinlineを付けた関数は高速呼び出し(実現方法は任意)を目指すというわけです。 > > プロセッサ依存の関数ベクタ > よく分からないので勉強します 通常、関数を呼び出すには16~64ビット程度のアドレスを指定する必要があります。それを、関数ベクタ(関数のアドレスを集めたテーブル)に予め登録しておき、何番目の関数というように(ハード的に)指定すれば、もっと効率よく関数を呼び出せます。 他には、絶対アドレスではなく、相対アドレスで指定すれば、関数呼び出しを効率化できる可能性があります。
その他の回答 (6)
- Quant
- ベストアンサー率18% (23/122)
#3です。 私がアセンブラを組んでいたときは、OSがプロセスに割り当てたメモリの下位番地がスタックに割り当てられるので、特別スタックをプログラマが意識する必要はなかったように思います。今は変わっているんですかね。 ただ自動的に割り当てられたスタックには限りがありますので、再帰の階層が深くなりすぎると、スタックオーバーフローのエラーが出ますので、そのときは、プログラムをリンクする段階でスタック領域を確保できるようにたいていのコンパイラはなっていました。
- jacta
- ベストアンサー率26% (845/3158)
末尾再帰の場合にはループに展開できる可能性があることは既に回答が出ている通りです。 他に、再帰関数の引数の一部が定数であれば、関数の定義次第ではインライン展開できる可能性があります。 もし、引数の全部が定数であれば、単なる右辺値になったり、関数内での副作用の部分だけが直接インライン展開される可能も、「原理的には」考えられます。 > C以外の言語でも、再帰関数のインライン展開が出来るプログラム言語があれば教えてください。 C++とか(多分期待している答えは違うんでしょうね)。 C言語もC99でinlineが標準でサポートされるようになりましたが、C++のinlineとは微妙に仕様がことなります。 C++では文字通り(可能な限り)インライン展開させるための機能ですが、C99では(可能であれば)通常より高速に呼び出す方法を採用させるための機能です。それはインライン展開でもよいですし、プロセッサ依存の関数ベクタを使ったり、ハード的な機能を利用したり、関数の定義によって方式を選択したりしても構わないわけです。
お礼
C言語とC++とではインライン展開の仕様が違うんですか。 > C++では文字通り(可能な限り)インライン展開させるための機能 というのは、最適化をせずに、明示的にインライン指定をしなくても自動でインライン展開(可能な限り)をしてくれるということですね。 逆にCでは最適化をするかインライン指定をしないとインライン展開(可能な限り)をしてくれないということですか? > プロセッサ依存の関数ベクタ よく分からないので勉強します ありがとうございました。
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
普通はできないです。 引数の受け渡しによる値の保持をするスタックを自前で作ればいいのかもしれませんが、なにやってんだかわかんないですよね。 それに、もしインライン展開できるとしても、インライン指定した関数がコンパイラによってインライン展開されるかどうかはわかりません。 もともとできるかぎりインラインにしてねという指定だからです。 大抵の場合、再帰関数はループに置き換えできると思うので、初めからループとしてコーディングした方がいいと思います。
お礼
自前でスタックを作るのは訳が分からなくなりそうですね。関数コールのオーバーヘッドが気になるようなら素直にループ構造に置き換えたほうがいいですね。
- Quant
- ベストアンサー率18% (23/122)
長い間アセンブラでプログラムを組んでいないので、自信ありませんが、再帰関数の場合、スタックで引数のやり取りをするぐらいで、他の処理は普通の関数と同じだったと思います。
- xcrOSgS2wY
- ベストアンサー率50% (1006/1985)
一般論として、再帰関数は次のような方法によるインライン展開が可能です。 (1) あらかじめ決めた数段分だけ展開する 例えば「f()がf()を呼ぶ」かわりに、f()のコピーを2つ作成しておき「f()がf2()を、f2()がf3()を、f3()がf3()を呼ぶ」ように展開します。(常にこのような展開が可能なわけではありません。) すると、f()→f2()とf2()→f3()の各呼び出しは再帰ではない普通の関数呼出になるので、f()とf2()は通常の関数と同様のインライン展開が可能になります。 このような形にすることで、ループアンロールと同様のメリットがあります。 (2) 「終端再帰関数」を単純ループに置き換えて展開する 終端再帰関数とは、関数実行の最後で再帰呼出を行う再帰関数のことです。このような形の関数の場合、これを再帰ではなく単純ループの形に書き換えることが可能です。(常に可能なのか、あるいは正確にはどのようにして「終端再帰」を見分けるのか、という厳密な定義は知りません。) ですので、再帰関数が終端再帰関数であれば、単純ループに置き換えた上で通常の関数と同様のインライン展開が可能になります。
お礼
(1)では階乗計算などで実現できそうですね。 (2)ではインラインで出来ない再帰構造は「終端再帰」に変えた方がいいということですね。(オーバーヘッド軽減のため) 「終端再帰」というのがよく分からないので勉強してみます。 ありがとうございました。
- rabbit_cat
- ベストアンサー率40% (829/2062)
普通はできないです。 ただし、いわゆる末尾再帰は、ループに展開できます。 Lisp,Schemeなどの関数型言語では、ほぼ必須の機能です。 C++等では、実現している処理系と思いますが。 末尾再帰でないループは、スタックを自前で作ることでループに展開できますが、これを自動的にやってくれる最適化機能は、多分ないと思います。
お礼
> いわゆる末尾再帰は、ループに展開できます。 末尾再帰がよく分からないので勉強します。 末尾再帰に修正したい場合は自力で修正しないといけないんですね。 関数設計時に末尾再帰を頭に入れておかないといけないですね。 ありがとうございました。
関連するQ&A
- 手続きのインライン展開 基準
コンパイラ型言語における手続きのインライン展開についてです。 例えばC++の場合、inline指定子をつけるなどしてインライン展開を促しますが, 長い手続きの場合はインライン展開されないと記憶しています。 お尋ねしたいことは2つあります。 1つ。1箇所でしか呼び出されない手続きの場合、どんなに長くても、インライン展開したほうがより最適なプログラムになるのではないか? 2つ。1箇所でしか呼び出されない手続きの場合、最適化モードでコンパイルするなりインライン展開指定するなりすれば、インライン展開は行なわれるか? 暇な時にでも、どなたか教えていただけたら幸いです。
- ベストアンサー
- その他(プログラミング・開発)
- インライン展開でコンパイラが何をやっているのか知りたいです
インライン展開すると、関数の呼び出しオーバーヘッドが小さくなることはわかるのですが、インライン展開した場合としていない場合と、なぜ関数呼び出しのオーバーヘッドがなくなるのかアセンブルレベルでの違いがよくわからないです。 関数をインライン展開した場合、コンパイラはどのようにコンパイルするのか、そしてその関数実行時の振る舞いがインライン展開なしの場合とどう違うのか、わからないので教えていただけませんか? 以上、よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 再帰的な関数の作り方
C言語の勉強をしている初心者です。 まだまだ始めたばかりでよく分かっていない状態です。 再帰的な関数が便利そうな事が書かれているのをよく目にしますが、何が便利でどう作ればいいのか分かりません。 分かりやすく教えていただけませんか。
- ベストアンサー
- C・C++・C#
- インライン関数
インライン関数として認識されなくても、通常の関数として実行されるのなら、プログラムする際にはすべての関数にinlineと書けばいいと思います。 インライン関数を使えば実行速度が上がる。それなら何故コンパイラ側で通常の関数すべてをインライン関数として認識しないのかがわかりません。inlineと書く手間が省けるので。 lnline関数として認識しようとしたができず、通常の関数として実行する時は、通常の関数を普通に実行するときよりも実行速度が遅くなるのでしょうか?もし、遅くならないのならすべての関数をinline関数として書けばいいと思います。どうなんでしょうか?お願いします。
- 締切済み
- C・C++・C#
- インライン展開されているか確認する方法
VisualStudioを使用しています。 タイトルの通り、関数がインライン展開されているかどうかを確認したいのですが、何か方法はあるのでしょうか? void func(){ int a = 0; } void main(){ func(); } 例えば、上のコードで関数func()がインライン展開されてるかどうかを知りたいと思います。 どうかよろしくお願いします。
- ベストアンサー
- C・C++・C#
- C++でforや再帰関数を使わずに、総当りする方法はありますか?
C++等で、forを使わず、再帰関数を使わずに多量のループで総当りする方法はありますでしょうか? 自己末尾再帰関数というのがネットで出てきますが、C言語系では使えないみたいです。 再帰関数で変数を全てスタティックにしても、関数の多重呼び出しで容量を食ってプログラムが動かないほどの計算をこなす必要があるのですが、こういった多数の桁のやり方になれておらず、先が見えません… また、全部をforにするのも、桁が大きすぎて問題があります。 どなたかご教授くださいますと幸いです。
- ベストアンサー
- C・C++・C#
- sinのマクローリン展開
再帰的関数定義とsin(x)のマクローリン展開の初めの10項を用いてsin(x)の近似値を出力するプログラムを作成せよ。 という問題で、マクローリン展開は分るのですがプログラムに出来ません…。 関数まで習っていて、配列などはまだ習っていないのですが、 どうやれば良いのかどなたか教えてください_| ̄|○
- ベストアンサー
- C・C++・C#
- 再帰関数のサポートについて
http://ja.phptherightway.com/pages/Functional-Programming.html 上記ページにありますようにPHPは再帰関数をサポートとあります。 関数プログラミングなるものはこの再帰関数を使ってループをつくったりすると ききました。 たとえば function roop($i){ print($i); $n = $i + 1; if($n < 100){ roop($n); } } roop(1); というようなコードでしょうか。 これは1~99までのループですよね。 これはPHPがインタープリターといえど、一度 PHP専用のバイトコードに変換して からPHPエンジンがバイトコードを実行するため再帰が可能という解釈でもんだいないですかね? もしほんとうに逐次解釈なインタープリターなら解釈途中に、その関数自体の定義をインタープリターが認識? し終わる前に未定義状態の関数が出現してしまうってことですよね? undefined な関数があるといようなエラーがでてくのでしょうか? 生Cのソースみればわかるのでしょうけれども、私はCがわからないので・・・。 概要でよいのでご教授ください。
- ベストアンサー
- PHP
お礼
私自身プログラミングは上位アプリケーションしか作ったことがなく、インライン展開も「オプティマイザで出来ればインラインしとこう」くらいでした。 分からないキーワードがたくさん出てきたのでもっと勉強します。 とても参考になりました。ありがとうございました。