再帰的プログラムを設計する

Question

私はプログラミングの初心者ではありません。私は今、ほぼ3年間プログラミングしています。しかし、私はまだ再帰的プログラムの理解と設計については不満を感じています。時には、多くの時間を要するプロセス全体を書き留める必要があります。 は、このプログラムを言う： 平衡二分探索木

にソートされた配列に変換

TreeNode* sortedArrayToBST(vector<int>& nums) { 
     return help(nums, 0, nums.size()-1); 
    } 

    TreeNode* help(vector<int> &nums, int start, int end){ 
     int size=end-start; 
     if(size<0) return NULL; 
     if(size==0) return new TreeNode(nums[start]); 
     int mid=(start+end)/2; 
     TreeNode* root=new TreeNode(nums[mid]); 
     root->left=help(nums, start, mid-1); 
     root->right=help(nums, mid+1, end); 
     return root; 
    } 

私はどのようにツリーの形を追跡する非常に苦労を持って....そして、私は間違いなくこのようなプログラムを自分でデザインすることができません。私はすでに30の再帰的なプログラムを見てきました。私はそれに精通するためにもっと練習をする必要があることを知っています。あなたが再帰的なプログラムを設計するときの考え方プロセスと再帰的なプログラムを素早く理解する方法を知りたいだけです。 多くの多くのありがとう!!

Answer 1

あなたは心の中で4つの物事を保つために必要な再帰を扱う：

• 現在の状態を定義するパラメータは何ですか。
• 終了条件とは何ですか？
• コールは何を返しますか。
• どのように再帰呼び出しの結果を組み合わせて、現在の呼び出しに対する回答を生成しますか？

あなたが言及した場合。

• パラメータは、リストのセクション（開始、終了）の座標です。
• 終了条件：リストセクションが空です。リストに1つの要素がある場合は、その要素だけのツリーを返します。
• 返された結果：パラメータからリストのセクションを表すルート完全に構築されたバランスツリー。
• 結果を結合する方法：中点をピックアップしてツリーのルートにします。左の子を、開始点と中間点の間のサブセクションのツリーのルート（そのリストの再帰呼び出し）に設定します。右の子を、リストの中間点と終点の間のサブセクション（そのリストの再帰呼び出し）のツリーのルートに設定します。

これら4つの点について明確である限り、ほとんどの再帰的な問題は簡単になります。あなたがより良くなるためには、再帰を含むより多くの問題を練習する必要があります。