Hatena Blog Tags

はてなブログ トップ
再帰
このタグでブログを書く

言葉の解説

ネットで話題

関連ブログ

再帰

(コンピュータ)
【さいき】

︻recursion︼
ある対象xの定義にx自身を使用することを再帰といい、そのような定義を再帰的定義という。もちろん、そのような定義は定義として成立する場合としない場合があり、再帰的定義が本当に定義になっていることは証明が必要である。
再帰は、プログラミング言語におけるデータ構造や関数の定義に用いられることが多い。関数の場合は、自分自身を繰り返し呼び出して、呼び出した順に処理が行われて再び帰ってくることから、﹁再帰﹂という名前がつけられたのであろう。
数列の漸化式は再帰的定義の一種である。通常は右辺の添字が左辺の添字より常に小さく、自然数である添字が無限に減少することはありえないので、定義として成立することがわかる。
再帰により定義されたデータ構造は再帰的データ構造ないし再帰データ構造と呼ばれる。リストや木は再帰データ構造の例である。
再帰により定義された関数は再帰的関数ないし再帰関数と呼ばれる。再帰関数の定義が定義として成立していないと、実行した場合の現象としては無限ループになる。
再帰データ構造に対する処理は、再帰関数を用いると自然に記述できることが極めて多い。
このタグの解説についてこの解説文は、すでに終了したサービス﹁はてなキーワード﹂内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

勉強のあしあと•6ヶ月前

再帰 - recursion (Java 第２回)

はじめに このページは大学のJavaの授業の予習の一環で書いている。 直感的な理解をメモしているだけなので、厳密な内容は避ける。 第２回は再帰である。 再帰とは 再帰とは、ある関数が関数内で自分自身を呼び出すこと。 より一般的には（プログラミングの文脈でない場合）、ある言葉の定義の中にその言葉自身が登場することである。 再帰を用いて、ソースコードを簡潔にできる場合がある。 再帰の解説 以下のコードは、階乗(factorial)の表示のメソッドと、階乗の計算のメソッドが含まれたコードである。 public class Recursion { public static void main(Str…

#Java#プログラミング#再帰

関連ブログ

競技プログラミング日記•1年前

AtCoder Beginner Contest 266E


ABC266E 期待値DP. 素直に考えると再帰になる． 再帰で考えた後に，高速化として for などが可能か考えればよい． 最初から綺麗に書こうとしない方が楽． 残り \(x\) ターンのときの答えを \(f(x)\) とおく．\(f(x) = \sum_{d \in [1,6]} \frac{1}{6} max(d, f(x-1))\)\(f(0) = 0\)となる． ここで，\(f(0)\) はサイコロの任意の目より小さければ何でもよい． \(max(d, f(0))\) の部分で \(d\) が採用されれば何でも良いから． または，\(f(0)\) を考えるのが心配なら \(f(1) …
#AtCoder#AtCoder Beginner Contest#期待値DP#再帰
おっさんの備忘録•1年前

再帰関数（Rucursive Function）


再帰︵Recursion︶ ある物事について記述する際に、記述しているもの自体への参照が、その記述中にあらわれること。つまり、再帰関数はある処理を実行中にそのある処理があらわれること。⇒関数内で自身を呼び出す関数。 public void ProcessA() { ... ProcessA(); // 自身 ... } 終了条件 上記のProcessAを考えると、1回目のProcessAで、2回目のProcessAを呼び出し2回目のProcessAで、3回目のProcessAを呼び出し3回目のProcessAで、4回目のProcessAを呼び出し ... のように、永遠に続いてしまう(無…
#アルゴリズム#スタック#再帰
雑記簿帳・調法調度•1年前

"再帰関数の大川隆法です．スゥ…「" itakogei(); "」"

#include <iostream> using namespace std; void itakogei(){ cout << "再帰関数の大川隆法です．スゥ…「"; itakogei(); cout << "」" << endl; } int main(void){ itakogei(); }

#ネタ#再帰#再帰関数#再帰呼び出し
貳佰伍拾陸夜日記•2年前

関数の再帰的な定義に名前付けは必要か

結論から言うと, 名前を付けることなく再帰的な関数を定義することは可能. 特定のプログラミング言語でどうかというよりは抽象概念としての関数の再帰を名前なしに実現可能かどうかという話(名前なしに実現できるプログラミング言語は存在するかという話). 発端 id:naoyaさんがこういうツイートをしていた.再帰を書くときに何気なく関数に名前つけたり let で束縛したりしてたけど「再帰には三項関係が必要でありその実現には記号が本質的に関わる」とあり、名前づけの行為が必然だったことが分かった。プログラミングするときの視点が変わるな— naoya (@naoya_ito) 2022年8月12日

#ラムダ計算#再帰
イバコの生存記録•3年前

47. ラムダ式の再帰を書きたかった話


仕事でコードを書いていて、ふとラムダ式で再帰処理を書きたくなりました。 privateメソッドやローカル関数で定義すれば良いと言えばそうなのですが、その場限りの微妙に複雑な処理なので変数にバインドしたかった感じです。通常のメソッドでは以下のように再帰を書きます。 int Factorial(int n) { return n == 0 ? 1 : n * Factorial(n - 1); } 当然ですが、このようにメソッド名が必要になります。よって、ラムダ式で再帰を書くのは一見無理そうです。しかし、C# では以下のように書くとラムダ式の再帰を実現できるようです。 void Hoge() { …
#C##ラムダ式#再帰
なんか考えてることとか•3年前

Haskellで再帰を心置きなく書いて良い理由

2022/9/18 「末尾再帰最適化」を「末尾呼び出し最適化」に修正 「サンク」関連の怪しい言い回しを修正 その他微妙な表現を修正 Haskellのような純粋関数型プログラミング言語では基本破壊的代入が許されていないために、ループするための構文、または式が用意されていない。そのために、再帰を使ってループを表現する、というのが一般的となっている。しかし、手続き型言語に慣れたプログラマからすれば、それはとても不安になることでもある。今回、なぜ不安になるのかどうかについて解説するとともに、なぜHaskellでは再帰を用いても問題ないのか書いていこうと思う。

#Haskell#再帰#遅延評価
ALNEA note•3年前

言葉の少ない世界に生まれたら・・

RX100 M3 Vario-Sonnar T＊ 24-70mm F1.8-2.8 / 渋谷区 宇田川町 / 渋谷PARCO 屋上広場 / 2020.1.13 渋谷のギッシリ詰まった街並み。コンクリートの仕切りを立ててギュウギュウに押し込んだ街をガラス越しに眺める・・ 緊急事態宣言延長、そんな時は本でも読もう・・と言うワケで、最近読み始めた本がなかなか面白いので紹介しよう ww RX100 M3 Vario-Sonnar T＊ 24-70mm F1.8-2.8 / ピダハン「 言語本能 」を超える文化と世界観 / 2021.5.5 これね、『 ピダハン「 言語本能 」を超える文化と世界観 』み…

#ピダハン#再帰#ピダハン語#チョムスキー
コラッツ予想がとけたらいいな2•3年前

Paraphrase をやってみた　その2（ズンドコ）

サンプルにはズンドコキヨシのプログラムがあったので、 それを末尾再帰でやってみた。 > "zdkRec.pp" load ok. > zdk Doko Zun Doko Doko Doko Doko Zun Zun Zun Doko Doko Zun Doko Zun Doko Zun Doko Zun Doko Doko Zun Zun Doko Doko Doko Zun Zun Doko Zun Zun Doko Zun Doko Zun Zun Doko Zun Zun Zun Zun Zun Doko Ki-Yo-Shi!! ok.

#Paraphrase#再帰
TECHSCORE BLOG•16時間前

AWS CloudFormation のネストしたスタックのエラーを探索するツールの紹介

はじめに AWS CloudFormation を使用してインフラを管理する際、エラー箇所を特定することが手間です。 特にネストしたスタックでは、ブラウザ上の AWS コンソールから多くログを確認しつつスタックを辿っていくのでかなり煩雑になります。 今回は、このような問題を解決するために開発した「cfn-error-detector」というツールを紹介します。 cfn-error-detectorとは cfn-error-detector は、AWS CloudFormationの デプロイメント失敗の根本原因を検出するためのコマンドラインツールです。複雑なネストされたスタック内でもエラーのあ…

Imaginantia•1日前

雑記240725　ビジュアルプログラミングについてのあれこれ


https://t.co/xV8dDpT4NJ— Baku⌇麦 (@_baku89) 2024年7月24日 Sainaさんとちょっと話したりもしましたが、色々思うことあるので書きたいなと思いました。 が、どうにも私の語彙が圏 (あと Haskell) に寄りすぎていて丁寧に説明するのがほぼ不可能でした。 なので、ある程度は諦めつつ、事例ベースで書いてみます。 あと文章にするのも難しかったので、箇条書きスタイルで書きます。 本当に雑多ですが… Sainaさんのツイート 独り言メモう～ん、突っ込んでくれる人がいたら突っ込んで欲しいです... pic.twitter.com/R7UB41FPZP— …
kawairiya’s blog•1日前

チュインチュイン


なにか言いたいのに、なにも気の利いたことがいえなそうだとすぐチュインとか言っちゃうの、脳の劣化かも。大人の相槌が全部同じな理由が期せずしてわかってしまった。こんなこと、知りたくなかったのに。 なるほどね～。へ～＾ 新聞も～韻踏むと みたいな、韻あるじゃないですか。こういうの好き。GNUみたい。 すみません、再帰的頭字語みたいな自己言及好きで。 ここで、僕の好きなメタネタ小説紹介します。 これ読んで。 あとなんだろう。めだかボックス読んで。 症年症女っていう漫画が面白かったです。僕みたいなのが主人公で。←これ、自意識過剰でナルシストで特別な人間になりたがってる中二病の発言って思われがちなんですけ…
NRIネットコムBlog•2日前

Boto3で出てくるNextTokenとは何者か　～NextTokenとのうまい付き合い方～

本記事は AWSアワード記念！夏のアドベントカレンダー 13日目の記事です。 🎆🏆 12日目 ▶▶ 本記事 ▶▶ 14日目 🏆🎆 こんにちは、西内です。 この度、2024 AWS All Certifications Engineersに選出していただきました！ 今年も資格が新たに3つ追加されましたが、引き続き維持できるよう頑張ります！！ そして、来年のswagは更に豪華になっていることを期待しています...！ （Amazonのギフト券とかもらえないかなあ～） AWSのAPIを実行したときに見るアレ NextTokenとは何者か NextTokenとの付き合い方 その１ whileを使う Ne…

MRが楽しい•2日前

Unityでスクリプトからオブジェクトのレイヤーを変更する

本日はUnityの小ネタ枠です。 Unityでスクリプトからオブジェクトのレイヤーを変更する方法です。 GameObject.layer ゲームオブジェクトが存在するレイヤーを参照・設定できます。 0 から 31 までの値が設定可能です。 docs.unity3d.com サンプルスクリプト 自身の子オブジェクトを全て指定名のレイヤーに切り替える以下のサンプルスクリプトを作成しました。 ・LayerSetTest.cs using UnityEngine; public class LayerSetTest : MonoBehaviour { [SerializeField] private …

Python学習チャンネル by PyQ•3日前

Pythonのpathlibモジュールを使おう

こんにちは、PyQチームです。 Pythonでファイルやディレクトリを扱うモジュールとして、osモジュールとpathlibモジュールがあります。 これらのモジュールはどちらもPythonの標準モジュールですが、新しいpathlibモジュールはosモジュールよりも使いやすくなるように設計されています。また、Python 3.12でpathlibにいくつもの修正が加わりました。 今回は、pathlibモジュールの使い方を簡単に紹介します。 pathlibモジュールは、パスをPathで表現 Pathオブジェクトの作成とパスの連結 ディレクトリの作成 パスの連結 ファイルへの書き込み ファイルからの読…

虎の穴開発室ブログ•3日前

「関数型デザイン」を読んで、設計と実装の幅を広げよう！


当ブログを見ている皆さん、こんにちは。虎の穴ラボのy.fです。 本記事は虎の穴ラボ2024年夏の連載企画、23日目の記事です。 昨日はS.Sさんの﹁﹁システム設計の面接試験﹂で最適なシステム設計を学ぶ﹂が公開されました。ぜひご覧ください！ 次は山田さんの﹁エンジニア組織を強くする 開発生産性の教科書﹂が公開されますので、こちらもご期待ください！ 今週のテーマは﹁書評﹂ということで、最近出版された﹁関数型デザイン﹂という本を読んでみたので書評を書いていこうと思います！ store.kadokawa.co.jp 本書を読んだ理由 まず本書は、関数型プログラミングの本であるとともに、Clojureに…
ilovetrend’s diary•3日前

マツコの知らない世界（7月23日）の日傘の世界の種類｜ブランド・メーカーは？

マツコの知らない世界（7月23日）の『日傘の世界』で日傘について紹介しています。 「自宅に230本コレクションする傘ソムリエが語る…真夏の必需品日傘」として生地進化がすごい日傘などが紹介されていました。 生地進化がすごい日傘トップ3｜マツコの知らない世界の日傘 2024年7月23日放送の「マツコの知らない世界」の「日傘の世界」で紹介された日傘は以下の通りです。 COKAGE+ 木手元55cm ジャンプ折（東レ） 【予約/予約特典付】KAGE＋ 影が伸びる 折りたたみ傘 晴雨兼用（GODO DESIGN カゲプラス 大きめ 濡れない UVカット 雨傘 日傘 cokage 日傘 丈夫 頑丈 防水 …

fltech - 富士通研究所の技術ブログ•3日前

ICML2024 にて「アクション説明を考慮した決定木および木アンサンブルの学習技術」について発表します

はじめに こんにちは．人工知能研究所の金森です． 富士通研究所では「説明可能AI（XAI）技術を用いた意思決定支援」に関する研究開発を行っており，現実世界の意思決定タスクへの適用（例えば，エンゲージメント調査データに基づいた従業員の生産性向上アクションの発見）に取り組んでいます． このたび，我々の研究成果である「アクション説明を考慮した決定木および木アンサンブルの学習技術」に関する研究論文が，機械学習分野の主要な国際会議である ICML2024 に spotlight 論文（投稿論文の上位3.5%！） として採択されたので，その内容を紹介します． 対象論文 タイトル: Learning Dec…

すたいるのOBS情報メモブログ•3日前

OBS Studio 30.2 リリースノート【翻訳】

以下の内容は OBS Studio 30.2.0 / 30.2.1 / 30.2.2 リリースノートを日本語に訳したものです。 変更内容が気になる場合はご覧ください。 誤字脱字、誤訳などありましたら コメント までお知らせください。 記事投稿日 2024年06月09日、最終更新日 2024年07月24日 02時45分頃

Technically Impossible•3日前

F#でのメモ化 - クロージャからスレッドセーフ、複数の引数対応まで


F#での再帰処理と一緒に言及される、定番の話題がメモ化だ。よくあるのが、フィボナッチ数を求める処理をメモ化するのではなく、その関数自体をメモ化する話題だ。昨日の話題*1は、前者に言及している。今回の話題は、後者についてだ。特別な工夫なく、ロジック通りにフィボナッチ数を求めるコードを書けば、その処理は無用な重複処理を孕むことになる。一度計算した順位のフィボナッチ数は、再計算するのではなく、その計算結果を再利用して出力することで、処理を効率化できる。つまり処理のメモ化だ。同様に、複数回呼び出しされる関数について、その関数の出力結果と、その時の引数の組み合わせをメモして再利用すれば、やはり処理を効率…
アドラー心理学で一緒に考えてみませんか•4日前

カウンセリングのいらない人たち　～ピダハン～

おはようございます、鍵野です。昨日、九州北部、大分県も梅雨明けしたとみられると気象庁からの発表があったようですが、今朝も朝からクーラーに活躍してもらっています。みなさま熱中症にはどうぞ気を付けられて、水分補給もしっかり、今日もできることをやっていきましょう（で、朝からブログかい（笑））。 時給は下げてないけど収入はレーダーをかいくぐれるくらいの低空飛行を続けている鍵野です。ということは、大金持ちならぬ大時間持ち（笑）。まぁとりあえず食べていかれてるから、よしと安心しています。この安心というのはしっかり将来の見通しがあるという意味では決してなく、お釈迦さまでも未来はわからないのだから、今から心配…

MOSFET’s blog•4日前

Lisp言語とは何か

はじめに Lisp（リスプ）は、1958年にジョン・マッカーシーによって開発されたプログラミング言語です。名前は「LISt Processing」の略であり、リスト処理を中心に設計されています。Lispは、プログラミング言語の中で最も古い部類に入りますが、今でも幅広い用途で使用されています。 特徴 Lispの特徴には以下の点があります。 1. シンボリック表現 Lispはシンボリック計算のために設計されており、プログラム自身をデータとして扱うことができます。これにより、自己修正や自己拡張が容易になります。 2. リスト構造 Lispの中心的なデータ構造はリストです。リストは簡単に定義でき、操作…

Technically Impossible•4日前

F#でのフィボナッチ数列 - 再帰、メモ化再帰、末尾再帰


再帰処理の定番の一つがフィボナッチ数の算出だ。以前、別件で触れたように*1、ロジックの特性上、無数の重複処理が生じる。これらの重複を効率的に処理するための典型的な手立てとして、次の手法が挙げられる。 メモ化 計算済みの結果をキャッシュする 末尾再帰 インタプリタ、コンパイラによる最適化 前者は汎用的に機能する一方、キャッシュを併用するため、メモリ効率が悪い。後者はロジックの書き方だけでなく、インタプリタ、コンパイラに依存するため、汎用的に機能しない。しかし、より高速なパフォーマンスを期待できる。どのプログラム言語でも定番の話題なのだが、特にF#においては、フィボナッチ数の処理自体をメモ化するこ…