なあ、再帰関数好きな人いる？パート3 [転載禁止]©2ch.net

**デフォルトの名無しさん** · 2015/11/28(土) 18:51:38.86

なあ、再帰関数好きな人いる？

**デフォルトの名無しさん** · 2016/06/19(日) 20:41:14.58

>>719
そう言う時期が俺にもあったな...（遠い目）

**デフォルトの名無しさん** · 2016/06/19(日) 21:07:57.12

再帰で実装した方がスッキリするケースってなかなか出てこないから最近全く使ってないや

**デフォルトの名無しさん** · 2016/06/20(月) 12:26:15.09

再起なんてバグの温床だからなぁ
マインスイーパー作る時ぐらいしか使わない

**デフォルトの名無しさん** · 2016/06/20(月) 19:47:38.77

import Data.Function (on)
import Data.List (concatMap, groupBy)
main =
let (f:r) = mypi 2 4 1 12 4
s = slice 5 $ slice 10 $ concatMap show r
in putStrLn (show f ++ ".")
>> putStr (unlines $ map unwords $ take 200 s)
slice :: Int -> [a] -> [[a]]
slice n ls = let q = concatMap (replicate n) [0..] :: [Int]
in map (map snd) $ groupBy ((==) `on` fst) $ zip q ls
mypi :: Integer -> Integer -> Integer -> Integer -> Integer -> [Integer]
mypi k a b a1 b1 =
let p = k * k
q = 2 * k + 1
a' = a1
b' = b1
a1' = p * a + q * a1
b1' = p * b + q * b1
loop a a1 d d1 =
if d == d1 then
d : let a' = 10 * (a `rem` b' )
a1' = 10 * (a1 `rem` b1')
in loop a' a1' (a' `quot` b') (a1' `quot` b1')
else
mypi (k + 1) a b' a1 b1'
in loop a' a1' (a' `quot` b') (a1' `quot` b1')
えんしうりつを100まんけたひょうじする

**デフォルトの名無しさん** · 2016/06/20(月) 23:20:34.02

パイ焼きか？
何秒で計算できんの？

**デフォルトの名無しさん** · 2016/06/20(月) 23:52:55.90

$ time ./pi >/dev/null
./pi > /dev/null 0.40s user 0.00s system 99% cpu 0.400 total
一瞬やね(最適化 -O)
ちなアルゴリズムはRubyのソースについてるやつから持ってきた

**デフォルトの名無しさん** · 2016/06/27(月) 22:23:07.70

深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。

**デフォルトの名無しさん** · 2016/06/28(火) 10:17:41.97

幅優先探索の絶対見つかる感は異常

**デフォルトの名無しさん** · 2016/07/18(月) 23:29:48.39

まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど

**デフォルトの名無しさん** · 2016/07/26(火) 07:09:31.44

>>33
iがインクリメント出来ないw

**デフォルトの名無しさん** · 2016/07/26(火) 07:11:59.49

ディレクトリ掘っていく処理なら再帰の方がすっきり書ける
それ以外使ったこと無いけど

**デフォルトの名無しさん** · 2016/07/26(火) 07:14:06.40

Javaの例外の発生源を探すのにも使った

**デフォルトの名無しさん** · 2016/07/28(木) 22:29:51.78

flattenがあると再帰書かなくて済むことがまれによくある。

**デフォルトの名無しさん** · 2016/07/28(木) 23:29:35.59

findとかディレクトリのflattenだよね～

**デフォルトの名無しさん** · 2016/07/30(土) 09:51:23.93

再帰は楽しい

**デフォルトの名無しさん** · 2016/07/30(土) 22:01:40.05

超簡単なハノイの塔のコードを
理解出来ない奴らばかり

俺様ステキ

再帰は楽しい

**デフォルトの名無しさん** · 2016/07/30(土) 22:19:26.10

ハノイの塔って最初誰が考えたんだろなｗ
まさに再帰のための問題だよなｗ

**デフォルトの名無しさん** · 2016/07/31(日) 02:49:55.84

>>737
エドゥアール・リュカ/1800年代後半

**デフォルトの名無しさん** · 2016/07/31(日) 11:30:45.35

連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ？

**デフォルトの名無しさん** · 2016/08/01(月) 17:10:15.58

行列式の値を余因子行列から求めるって発想が好き

**デフォルトの名無しさん** · 2016/08/14(日) 09:13:25.49

数学のように条件を書くだけで処理が書けるのは楽しい

**デフォルトの名無しさん** · 2016/08/14(日) 12:23:51.18

>>741
では
これの値を教えてください

lim[n->∞]sin(πen!)

わりとまじです

**デフォルトの名無しさん** · 2016/08/14(日) 12:55:12.86

en==円

**デフォルトの名無しさん** · 2016/08/16(火) 08:58:30.09

順次反復分岐だけで超深いは凄いな

**デフォルトの名無しさん** · 2016/10/13(木) 18:45:18.08

>>693
これこそ C の最強な部分だ

**デフォルトの名無しさん** · 2016/10/13(木) 18:46:47.08

void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。

**デフォルトの名無しさん** · 2016/10/30(日) 02:58:18.76

斉木楠雄と再帰関数って似てるよな

**デフォルトの名無しさん** · 2016/10/30(日) 13:41:20.72

小町算の総当たり問題は綺麗にかけて好き

**デフォルトの名無しさん** · 2016/11/06(日) 03:07:23.35

昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ

**デフォルトの名無しさん** · 2016/11/06(日) 09:26:24.46

int main()
{
return main();
}

**デフォルトの名無しさん** · 2016/11/06(日) 12:42:18.20

>>750
なめてんの？

**デフォルトの名無しさん** · 2016/11/09(水) 21:10:33.07

再帰は面白いと思ってた時期もあった気がする。

ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか

**デフォルトの名無しさん** · 2016/11/09(水) 22:24:15.76

ハノイの塔

**デフォルトの名無しさん** · 2016/11/10(木) 13:14:57.02

>>752
んなわけない。明らかに別物

**デフォルトの名無しさん** · 2016/11/10(木) 13:24:06.83

ただのループでスタックオーバーフローの心配はないからなぁ

**デフォルトの名無しさん** · 2016/11/10(木) 13:27:48.38

x 再帰はループの一つ
x ループは再帰の一つ

o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる

**デフォルトの名無しさん** · 2016/11/10(木) 14:27:23.84

>>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。

**デフォルトの名無しさん** · 2016/11/10(木) 14:50:09.90

djnz派でした

**デフォルトの名無しさん** · 2016/11/10(木) 18:03:12.84

再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する

**デフォルトの名無しさん** · 2016/11/10(木) 18:13:46.76

>>758
あー、ループあるな。そういう意味では。
すまんかった。

**デフォルトの名無しさん** · 2016/11/10(木) 19:18:34.28

天才じゃないから再帰使うわ

**デフォルトの名無しさん** · 2016/11/10(木) 19:25:25.72

>>755
再帰と同じようにループを実装すればオーバーフローしますけど。

>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。

ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。

まずこうゆうときは、E（電力）あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。

再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。

**デフォルトの名無しさん** · 2016/11/10(木) 19:26:27.18

ループって動的ループね

**デフォルトの名無しさん** · 2016/11/11(金) 06:56:11.81

>>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ？

**デフォルトの名無しさん** · 2016/11/11(金) 07:27:43.35

分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね

**デフォルトの名無しさん** · 2016/11/11(金) 07:50:29.58

質問ってとっちゃったか w

**デフォルトの名無しさん** · 2016/11/11(金) 07:54:13.90

再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。

**デフォルトの名無しさん** · 2016/11/11(金) 08:11:51.46

スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。

**デフォルトの名無しさん** · 2016/11/11(金) 09:50:34.09

>>767
int main(){ return main(); } 簡単です

**デフォルトの名無しさん** · 2016/11/11(金) 11:06:28.50

C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに

**デフォルトの名無しさん** · 2016/11/11(金) 11:08:28.85

珍珍が再帰不能です

**デフォルトの名無しさん** · 2016/11/11(金) 12:05:55.04

>>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。

**デフォルトの名無しさん** · 2016/11/11(金) 12:26:09.96

>>770
C++で、クラス内に関数を定義すりゃいいだけ

**デフォルトの名無しさん** · 2016/11/11(金) 13:51:46.35

ではstosbで

**デフォルトの名無しさん** · 2016/11/11(金) 19:18:44.95

>>774
メモリアクセス要るようなループ書かんだろう…。ましてや再帰の展開で。

**デフォルトの名無しさん** · 2016/11/11(金) 19:31:33.99

>>770
なるほどね，コンパイル単位内だけで末尾再帰を保証するわけだね

**デフォルトの名無しさん** · 2016/11/11(金) 20:38:07.10

>>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ

**デフォルトの名無しさん** · 2016/11/12(土) 15:29:28.13

コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か

**デフォルトの名無しさん** · 2016/11/13(日) 23:43:06.28

木構造をループで辿りたいときってスタック使わずにできる？

**デフォルトの名無しさん** · 2016/11/13(日) 23:46:50.63

辿るだけ（構造を保持しなくていい）ならできるでしょ
たとえば全てのアドレスを出すだけとか

**デフォルトの名無しさん** · 2016/11/14(月) 09:15:00.34

スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。

**デフォルトの名無しさん** · 2016/11/14(月) 10:59:32.44

ツリーだってメモリがツリー状になってる訳じゃない罠

**デフォルトの名無しさん** · 2016/11/15(火) 06:36:20.67

質問スタックを使わずにできるか
回答オーバーフローしない理由にはならない

意味不明

**デフォルトの名無しさん** · 2016/11/15(火) 07:51:46.25

できるよ

**デフォルトの名無しさん** · 2016/11/15(火) 10:35:05.01

>>784
関数呼び出しどうやってするんだよ
それにそんな再帰関数は好きになれないな

**デフォルトの名無しさん** · 2016/11/15(火) 10:52:21.24

日本語でおｋ

**デフォルトの名無しさん** · 2016/11/15(火) 13:01:02.10

>>786
ニーハオ！
モドルサキハドコニキヲクシマスカ？

**デフォルトの名無しさん** · 2016/11/15(火) 14:10:56.00

>>779-782

**デフォルトの名無しさん** · 2016/11/15(火) 15:51:11.27

アイヤー！

**デフォルトの名無しさん** · 2016/11/15(火) 20:24:10.55

>>779
http://codepad.org/Grt3NsIV
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14142251704

**デフォルトの名無しさん** · 2016/11/16(水) 02:58:25.42

codepadって年はでないのか

**デフォルトの名無しさん** · 2016/11/16(水) 22:36:41.79

ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。　馬鹿には永遠に判らんだろうけど。

**デフォルトの名無しさん** · 2016/11/17(木) 11:34:22.18

情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。

**デフォルトの名無しさん** · 2016/11/17(木) 11:37:48.10

誰かの口真似したのかもしれないけどそれは完全に間違ってますよ

**793** · 2016/11/17(木) 11:44:39.48

>>794
上の行？下の行？それとも両方？

**デフォルトの名無しさん** · 2016/11/17(木) 12:42:43.08

下

**793** · 2016/11/17(木) 13:03:18.99

>>796
Prologですから再帰述語で関数ではありませんが、

repeat :- 割り込みあり,!.
repeat :- repeat.

の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。

**797** · 2016/11/17(木) 13:06:35.00

すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。

repeat.
repeat :- repeat.

**793** · 2016/11/17(木) 13:16:05.70

>>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。

**デフォルトの名無しさん** · 2016/11/21(月) 07:42:33.65

>>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。

**デフォルトの名無しさん** · 2016/11/21(月) 09:29:48.04

>>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。

**デフォルトの名無しさん** · 2016/11/21(月) 11:07:34.14

>>801
条件が良すぎる・・・

**デフォルトの名無しさん** · 2016/11/21(月) 21:05:43.87

>>790
で完璧な回答をみせたはずだが

**デフォルトの名無しさん** · 2016/11/21(月) 22:27:59.06

好きか嫌いかで言ったら好きだ
趣味以外では使わないけど

**デフォルトの名無しさん** · 2016/11/21(月) 23:45:17.54

当然、趣味限定だね

**デフォルトの名無しさん** · 2016/11/22(火) 08:09:17.87

再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの？
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの？

**デフォルトの名無しさん** · 2016/11/22(火) 11:35:40.81

スタックって言ってもメモリはリニアなんだぜ

**デフォルトの名無しさん** · 2016/11/22(火) 12:37:46.98

>>806
ループで実現したときはスタックに積まれない。

**デフォルトの名無しさん** · 2016/11/22(火) 13:14:00.96

>>808
実行系に頼らず自分でスタックを実装するってこどだろ
使用メモリ量が不定なのは一緒

**デフォルトの名無しさん** · 2016/11/22(火) 13:44:09.96

スタックが摘まれないなら別物でしょう

**デフォルトの名無しさん** · 2016/11/22(火) 13:48:40.05

抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。

抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。

**デフォルトの名無しさん** · 2016/11/22(火) 20:27:24.28

>>790
で完璧な回答をみせたはずだが

**デフォルトの名無しさん** · 2016/11/26(土) 09:43:28.08

>>811
再帰は、入れ子状の関数呼び出しで、呼び出す関数は全部同一だから、
コードは一つで良い。しかし、関数だから呼び出す度にスタックに情報を積むし、
戻ってくるまで、積んである情報をPOPできない。
ただし、関数が末尾に有る時、則ち、戻って来た情報に対して何らかの計算をしてから
情報を返すということがない関数に関しては、戻ってきた値を直接自分の戻す値に
できるわけだから、呼びだされた時の普通なら積む情報を積まずに済ませることが
できるかも知れない。こういうことを「実体」というのですないか？

**813** · 2016/11/26(土) 09:45:28.00

すみません。最後
こういうことを「実体」というのではないか？
です。

**デフォルトの名無しさん** · 2016/11/26(土) 12:00:32.51

>>813
なんでも継続
http://practical-scheme.net/docs/cont-j.html

**デフォルトの名無しさん** · 2016/12/10(土) 03:10:28.97

>>813
根本的には処理もデータも区別なく実体ってことでしょ。
ループ自体も関数自体も実体。

**デフォルトの名無しさん** · 2016/12/18(日) 21:34:26.37

なあ、継続好きな人いる？

**デフォルトの名無しさん** · 2016/12/21(水) 13:12:18.95

ああ例外出たらすぐ継続押すよ

**デフォルトの名無しさん** · 2016/12/22(木) 22:15:49.61

継続は再帰ほど市民権得てないからなぁ。
継続を深く理解しているプログラマは全体の１割に満たないんだろうな。

**デフォルトの名無しさん** · 2016/12/22(木) 23:45:06.84

単純に継続を保証してる言語が少ない

**デフォルトの名無しさん** · 2017/01/03(火) 17:56:54.67

物自体の実在性を議論してんのかよ
やっぱ再帰って難しいわ

なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net

なあ、再帰関数好きな人いる？パート3 [転載禁止]©2ch.net