递归与尾递归总结

2018-06-17 23:32:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  链表的逆置常作为应届生面试题,主要考察求职者对链表的理解,还有思维能力。逆置的思路主要是保存几个临时的指针变量,其实好多面试题都可以通过保存临时变量的方式来解决。对于此类问题,建议一定不要死记硬背,因为死记硬背一定会随着时间的推移而忘记,建议按照pPrev,pNode,pNext依次向后推移的思路理解的基础上记住。

  以下C++代码给出了两种实现,一种是循环,一种是递归。注意递归的时候要采用尾递归的形式。因为普通递归在调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。

  尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈,而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可,之前的可优化删去。

#include "stdafx.h"

struct ListNode
{
    int m_nData;
    ListNode* m_pNext;
};

// pPrev    pNode    pNext
// 正常实现
ListNode* ReverseList(ListNode *pHead)
{
    ListNode* pNode = pHead;
    ListNode* pReversedHead = NULL;
    ListNode* pPrev = NULL;
    while(NULL != pNode)
    {
        ListNode* pNext = pNode->m_pNext;// 保存当前节点的下一个节点
        if (NULL == pNext)
            pReversedHead = pNode;// 如果下一节点为NULL,则当前节点为反转后的头节点,记录

        pNode->m_pNext = pPrev;// 将当前节点的下一个节点指向已经记录的前一个节点,因为要反转嘛
        pPrev = pNode;// 现在要向右错位了,前一个节点成为了当前节点
        pNode = pNext;// 当前节点成为了当前节点的下一个节点
    }
    return pReversedHead;
}
// 递归实现
ListNode* ReverseSingle(ListNode* pNode, ListNode* pPrev)
{
    if (NULL == pNode)
    {
        return pPrev;
    }

    ListNode* pNext = pNode->m_pNext;// 保存当前节点的下一个节点
    pNode->m_pNext = pPrev;

    return ReverseSingle(pNext, pNode);
}

ListNode* ReverseListRecursive(ListNode *pHead)
{
    ListNode* pNode = pHead;
    ListNode* pPrev = NULL;

    return ReverseSingle(pNode, pPrev);
}

int _tmain(int argc, _TCHAR* argv[])
{
    int len = 10;
    ListNode *pHead = new ListNode;
    pHead->m_nData = 10;
    pHead->m_pNext = NULL;
    ListNode *pPrev = pHead;

    for (int i=0; i<len; i++)
    {
        ListNode *p = new ListNode;
        p->m_nData = i; 
        p->m_pNext = NULL;
        if (NULL != pPrev)
        {
            pPrev->m_pNext = p;
        }
        pPrev = p;
    }

    //ListNode *pReversedHead = ReverseList(pHead);
    ListNode* pReversedHead = ReverseListRecursive(pHead);

    return 0;
}

   尾递归可以参考:递归与尾递归总结。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++学习笔记-内存管理与指针

下一篇:SOUI界面库 添加 windows系统文件图标皮肤