首页 > > 程序设计 > C/C++ >

递归与尾递归总结

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

　　链表的逆置常作为应届生面试题，主要考察求职者对链表的理解，还有思维能力。逆置的思路主要是保存几个临时的指针变量，其实好多面试题都可以通过保存临时变量的方式来解决。对于此类问题，建议一定不要死记硬背，因为死记硬背一定会随着时间的推移而忘记，建议按照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;
}