设计一个递归程序

Question

我不是真正的编程新手，我已经编程快三年了。但是我仍然对理解和设计递归感到沮丧 programs.Sometimes 我需要把整个过程写下来，这需要很多时间。说这个程序：将排序数组转换为平衡二叉搜索树

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 件事：

定义当前状态的参数是什么。
什么is/are结束条件。
叫什么return.
如何组合递归调用的结果来为当前调用生成答案。

在你提到的情况下。

参数是列表的一部分（开始、结束）的坐标。
结束条件：列表部分为空你 return null，如果列表有一个元素你 return 一棵只有那个元素的树。
returned 结果：代表参数列表部分的根完全平衡树。
如何合并结果：选取中间点并使其成为树的根。将左 child 设置为起点和中间点之间的子部分的树的根（对该列表的递归调用）。将右 child 设置为列表中点和末尾之间的子部分的树的根（对该列表的递归调用）。

只要搞清楚这4点，大部分的递归问题都会变得简单。如果你想在这方面做得更好，你需要练习更多涉及递归的问题。

设计一个递归程序

design a recursive program

c++

algorithm

recursion

binary-search-tree