soraなりの日々 - fc2 -

こころにひっかかったもの

[c++]再帰だ、再帰!

id:koki-h さんに、せっかく sicp の勉強会のお誘いを
頂いてたのに行けんやった・・orz

lisp の環境は今から作りますんで、次回、
また誘ってください
と、話変わって。

今日、さっきこんなものを見つけた↓

[Joelに聞く、「優れた開発者」の要件・心構え・努力すべきこと]
http://codezine.jp/a/article/aid/2292.aspx




このエントリーをはてなブックマークに追加
いろいろな側面があると思いますが、私が成功する開発者か
判断するときに見るのは、ごく特定のことで、それは第一に
再帰が使えること、第二にポインタが使えるということです。
(中略)  -- joel

ほんとかい?joel

でも、たしかに再帰が"使える"、"使えない"には差が出てくるかも知れない。

で、サクッと無意味な再帰プログラムを書いてみる↓

#include <iostream>

using namespace std;

int recursive(int& n)
    {
    if (n >= 1000)
        {
        return n;
        }
       
    n++;
    return recursive(n);
    }

int main(void)
    {
    int nCnt = 0;
    cout << recursive(nCnt) << endl;
    return 0;
    }

その昔、再帰で必ず出てくる"ハノイの塔"の練習問題を解いて、
なんとか理解したつもりになって、当時やってた vb のシステムに
組み込んでドキドキしながらテストしたんだっけ。

もう6年くらいは前になるんだよなぁ。

そんで、再帰理解する前と後では結構考え方に広がりが出たと
思えるのはほんと事実。

でも、よくよく考えると c言語 では、結構珍しくないものなのかもね。

チェーン構造体(ネスト構造体?)とかで、NULL がある
末端までループするとかで使うのも良くやったし、良く見かけた。

チェーン構造体はこんなやつ↓
struct ST_TEST {
    int n;
    struct ST_TEST* pNext;
};

それに、quick sort再帰使うよね。
あ、でも、c++ だと stl 使って一行で終わるし、他の言語でも
似たようなものだろから quick sort とかもう書かない
(書いたことがない?)のかな、若い人は。

前に書いたやつquick sort 部分↓
void quick_sort(vector<int>& nList, int left, int right)
{
    int iCnt, jCnt;
    int pivot;

    iCnt = left;
    jCnt = right;
   
    pivot = nList[( left + right ) / 2];

    while ( 1 ) {
   
        while ( nList[iCnt] < pivot )
            iCnt++;
           
        while ( pivot < nList[jCnt] )
            jCnt--;
           
        if ( iCnt >= jCnt )
            break;
           
        int temp;
        temp = nList[iCnt];
        nList[iCnt] = nList[jCnt];
        nList[jCnt] = temp;
        iCnt++;
        jCnt--;
    }

    if ( left < iCnt-1 )
        quick_sort( nList, left, iCnt-1 );
       
    if ( jCnt+1 < right )
        quick_sort( nList, jCnt+1, right );
}

あと、そいえば、去年あるプロジェクトで使った apache xml project の
xerces-c++ のサンプルでも使われてたな。再帰。
たしかにノードの解析とかって処理をするには、再帰は向いてるよね。
(この前、人に説明するときに名前ど忘れしてた。。。年かな。)

んー、ダラダラと書いたけど、たしかに filter として使うには良いのかも?
このエントリーをはてなブックマークに追加

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://sora2hs.blog70.fc2.com/tb.php/285-df6faeaa
この記事にトラックバックする(FC2ブログユーザー)