アルゴリズムの再帰(1)

アルゴリズムの再帰(1)
最近事が多すぎて、完全に静かにして真剣に何かを研究する時間はめったにありません.コードを書くことに集中するたびに、いつも他のことに中断されます.まあ、日曜日に来て、やっと時間を割くことができましたJ
「コードの美しさ」の第1章では、正規表現に基づいて対応するテキストに一致する値を見つけ、戻り1を見つけ、戻り0を見つけられなかったというパターンマッチングに関する問題があります.具体的な実装を除いて、中の優美な再帰呼び出しは私を深く引きつけた.そこで、私は再帰を考え直し始めました.結局、細部までの思考が足りないことがあります.
再帰とは
私の印象の再帰は、関数呼び出し自体が予め定義された操作を完了することである.もちろん、再帰を終了する条件、コードロジック、パラメータなど、実際に関連する内容はもっと多いです.
再帰はスタックとして理解され、すなわち、呼び出しシーケンスはシーケンス構造の形態であり、後進先出の順序に従ってスタックに格納される.たとえば、このような呼び出しA()->B()->C()->D()が追加されると、スタック内の順序は次のようになります.
A() : int
B() : int
C() : int
D() : int
この例から,B,C,Dの名前をすべてAに置き換えることが,Aを再帰的に呼び出すすべてのプロセスであることが分かる.
1〜N個の自然整数の和をどのように計算するかの具体的な例を見てみましょう.
{1, 2, 3, 5, …, n}
解法一
現在の和を格納するグローバル変数を定義します.
具体的には

        int sum = 0;



 



        private void GetSum(int n)



        {



            if (n == 0) return;



            if (n < 0)



                throw new ArgumentException("Invalid input.");



 



            sum += n;



            GetSum(n - 1);



        }

 
この再帰論理には問題はないが,最終的なユーザとして,その上にさらにカプセル化して使用できる変数を多く定義している.もちろん、関数を書いて再カプセル化し、exposeというwrap後のバージョンを書くこともできます.
では、より良い解決策はありますか?
解法二
戻り値のある関数を定義します.
冒頭では,再帰がスタックに似ていることを紹介するので,再帰呼び出しも後呼び出しで現れる原則に従う.戻り値を加算すると、現在のn値のnより前のすべての値の和、すなわちn個の数の和を計算するだけでよい.例えば10個の数があり、現在のnは5であり、この層の再帰は5の和である.
まずコードを見てから、具体的な分析をします.

        private int GetSumWithReturn(int n)



        {



            if (n < 0)



            {



                throw new ArgumentException("Invalid input.");



            }



 



            if (n == 0)



                return 0;



 



            return n + GetSumWithReturn(n - 1);



        }

 
分析解法二

nが0未満である場合、不正な動作とみなされる.

nが0に等しい場合は、最小値が計算されたとみなされ、再帰を終了することができる.

は、現在のnの値とn-1の前の

を返す.
nが5に等しい場合、スタックの構造は以下のようになり、下から上を見てハイライトされた部分に注意する.(スタックの順番が逆になっているので、下から上を見て、下がスタックの頂上です)
Function Call
Function Body
GetSumWithReturn(5)
        private int GetSumWithReturn(int n)  //n = 5         {             if (n < 0)                                    {                 throw new ArgumentException("Invalid input.");             }               if (n == 0)                 return 0;               return n + GetSumWithReturn(n - 1);//5 + 10 = 15, return 15         }  
GetSumWithReturn(4)
        private int GetSumWithReturn(int n)  //n = 4         {             if (n < 0)                                    {                 throw new ArgumentException("Invalid input.");             }               if (n == 0)                 return 0;               return n + GetSumWithReturn(n - 1);//4 + 6 = 10, return 10         }  
GetSumWithReturn(3)
        private int GetSumWithReturn(int n)  //n = 3         {             if (n < 0)                                    {                 throw new ArgumentException("Invalid input.");             }               if (n == 0)                 return 0;               return n + GetSumWithReturn(n - 1);//3 + 3 = 6, return 6         }  
GetSumWithReturn(2)
        private int GetSumWithReturn(int n)  //n = 2         {             if (n < 0)                                    {                 throw new ArgumentException("Invalid input.");             }               if (n == 0)                 return 0;               return n + GetSumWithReturn(n - 1);//2 + 1 = 3, return 3         }  
GetSumWithReturn(1)
        private int GetSumWithReturn(int n)  //n = 1         {             if (n < 0)                                    {                 throw new ArgumentException("Invalid input.");             }               if (n == 0)                 return 0;               return n + GetSumWithReturn(n - 1);//1 + 0 = 1, return 1         }  
GetSumWithReturn(0)
                private int GetSumWithReturn(int n)  //n = 0         {             if (n < 0)                                    {                 throw new ArgumentException("Invalid input.");             }               if (n == 0)      //n = 0, then return 0.                 return 0;               return n + GetSumWithReturn(n - 1);         }