使用递归时候需要注意的问题

时间：2021-06-13 06:55:09

使用递归的时候应该注意不可使用后加，就是n++或者n--

因为在递归中使用n++作为最终跳出递归的语句时候回导致递归陷入死循环

因为首先程序自己调用自己的时候，先去执行自己调用自己的程序，一直处在自己调用自己的状态，导致在第一次调用自己的 时候就不能完成，所以后加或者后减操作是随着递归操作从后向前操作的。

 

下面的递归调用不使用乘除法或者循环的情况下实现0到n的累加

public class Solution {
    
    public int Sum_Solution(int n) {if(n==0)
            return 0;
        return n+=Sum_Solution(--n);
    }
}

上面就是很好的例子，将sum_solution()中修改成n--程序就会出现问题。

 

下面顺便梳理一下递归调用怎样实现数据累加或者累乘：

而本次的返回结果需要包括上一次的返回结果，并且加上当前的返回结果。核心就是每次需要加上当前的控制递归的变量，递归变量只能和一个变量相关。（不知道使用集合类行不行）

递归的控制变量有时候需要 

 

 

下面是一段实现查找二叉树中，找到第k小的数

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    int i=0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot!=null){
            TreeNode result=null;
            result=KthNode(pRoot.left,k);
            if(result!=null){
                return result;    //如果result不是null的，说明result中存在我们想向上抛出的结果，不需要向下进行的必要了（已经找到了），继续向上抛出
            }
            i++;
            if(k==i){
                return pRoot;     //确定向上抛出的是谁
            }
            result=KthNode(pRoot.right,k);
            if(result!=null){
                return result;
            }
        }
        return null;
    }
}

在这里需要考虑的一个就是如何实现最终结果的层层抛出，并且在找到之后停止递归查找

首先明确的是向上抛出的一定是TreeNode类型的，就是要在查找到第k个数的时候向上抛出在这个位置的TreeNode，

但是向上抛出的同时，需要有上层接受并且继续向上抛出（其实这个向上抛出的动作就有中断递归的效果），

总结上面就是返回的结果一定和递归的函数有着直接或者间接的联系

 

 

下面这段代码实现的是删除有序链表中的重复的，所有重复的都要删除一个不剩，突然发现可以实现有条件的递归，

    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode p;
        if(pHead==null || pHead.next==null) {        //如果第一个或者第二个是null，不需要执行递归直接返回 return pHead;
        }
        if(pHead.val==pHead.next.val)              //这个分支用于跳过链表中重复的部分，注意使用变量p，可以减少使用.next访问，增加代码的速度。
        {
            p=pHead.next;
            while(p!=null && p.val==pHead.val) {
                p = p.next;
            }
            return deleteDuplication(p);
        }
        else                                     //因为前面的重复节点都被删除，，所以如果这个节点和后面的节点不重复，他就是不重复的，需要保留，那就直接递归下一个节点
        {
            pHead.next=deleteDuplication(pHead.next);        //这里还要注意一点返回的处理，这里使用的从前到后的思想 return pHead;
        }
    }

 

 

 

 

递归的三大步骤：

（1）确定函数的功能

（2）确定函数的终止条件

（3）由函数之间的递归关系确定函数的返回形式（最难的一步）（还要注意递归中出现的重复问题，就像在斐波那契数列中的那样，使用数组实现，减少递归的重复的问题）

就上面的这个说说：其从前往后的形式，前面处理过，就调用它后面部分，一层一层的递归循环下去。直到达到结束条件返回

 

标签：

相关文章