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

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

递归：函数自己重复调用自己
迭代：利用变量的原值推算出变量的一个新值；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;
}