C++递归和迭代的区别，并举例说明[通俗易懂]

全栈程序员-站长 • 2022年6月1日下午10:00 • 未分类 • 阅读 42

大家好，又见面了，我是你们的朋友全栈君。

递归：函数自己重复调用自己
迭代：利用变量的原值推算出变量的一个新值；A不停的调用B
例子一：斐波那契数
递归（recursion):

#include <iostream>
#include <vector>
using namespace std;
int fab(int n)
{ 
   
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    if (n > 1)
        return fab(n - 1) + fab(n - 2);
}
int main()
{ 
   
    cout << fab(4) << endl;
    return 0;
}

迭代（iteration):

#include <iostream>
#include <vector>
using namespace std;
int fab(int n)
{ 
   
    int a = 0, b = 1, c = 1;
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    while (n > 1)
    { 
   
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}
int main()
{ 
   
    cout << fab(4) << endl;
    return 0;
}

例子二：反转链表
递归（recursion):

#include <iostream>
#include <vector>
using namespace std;
struct ListNode
{ 
   
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) { 
   }
};
ListNode *reverseList(ListNode *head, ListNode *pre)
{ 
   
    if (!head)
        return NULL;
    if (!head->next)
    { 
   
        head->next = pre;
        return head;
    }
    ListNode *temp = head->next;
    head->next = pre;
    pre = head; //pre其实是往后移一个
    return reverseList(temp, pre);
}
ListNode *createNodeList(vector<int> &vec)
{ 
   
    ListNode *prev = new ListNode(vec[0]); //prev始终指向标尾指针
    ListNode *prevHead = prev;
    for (int i = 1; i < vec.size(); i++)
    { 
   
        ListNode *next_node = new ListNode(vec[i]);
        prev->next = next_node;
        prev = next_node;
    }
    return prevHead; //prevHead始终指向第一个元素
}
int main()
{ 
   
    vector<int> m = { 
   1, 2, 3, 4, 5};
    ListNode *l = createNodeList(m);
    ListNode *res_l = reverseList(l, NULL);
    for (auto p = res_l; p; p = p->next)
    { 
   
        cout << p->val << " ";
    }
    cout << endl;
    return 0;
}

迭代（iteration):

#include <iostream>
#include <vector>
using namespace std;
struct ListNode
{ 
   
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) { 
   }
};
ListNode *reverseList(ListNode *head)
{ 
   
    ListNode *cur = head, *pre = NULL;
    while (cur)
    { 
   
        ListNode *temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}
ListNode *createNodeList(vector<int> &vec)
{ 
   
    ListNode *prev = new ListNode(vec[0]); //prev始终指向标尾指针
    ListNode *prevHead = prev;
    for (int i = 1; i < vec.size(); i++)
    { 
   
        ListNode *next_node = new ListNode(vec[i]);
        prev->next = next_node;
        prev = next_node;
    }
    return prevHead; //prevHead始终指向第一个元素
}
int main()
{ 
   
    vector<int> m = { 
   1, 2, 3, 4, 5};
    ListNode *l = createNodeList(m);
    ListNode *res_l = reverseList(l);
    for (auto p = res_l; p; p = p->next)
    { 
   
        cout << p->val << " ";
    }
    cout << endl;
    return 0;
}