算法交作业之循环和递归(二)

说明：

循环是学习编程过程中的不可或缺的一部分。同时递归同循环有着千丝万缕的关系。

求和函数示例：

//求0到n的和。求和失败返回-1.否则返回结果。
#include <iostream>
//最常见的循环写法。
long long Sum(unsigned int&& n)｛
    long long sum = 0;
    for (unsigned index = 1; index <n+1; ++index)
        sum += index;
    return sum;
}
//递归写法
long long _Sum(unsigned int&& n){
    if (n == 0)
        return 0;
    return _Sum(n - 1)+n;
}
//最聪明的写法
long long __Sum(unsigned int&& n){
    long long sum = (1 + n)*n / 2;
    return sum;
}
int main(){
    int a = 10;
    std::cout << Sum(std::move(a)) << std::endl;
    std::cout << Sum(10) << std::endl;
    std::cout << _Sum(10) << std::endl;
    std::cout << __Sum(10) << std::endl;
    system("pause");
    return 0;
｝

相关解释：
1.采用long long 避免越界。
2.采用unsigned 避免出现负数。
3.用C++11标准书写。

查找函数示例：

#include<iostream>
#include <assert.h>
int Find_Array(const int * const arr, const unsigned& length, const int& value){
    if (arr == nullptr || length == 0)
        return -1;
    for (unsigned index = 0; index < length;++index)
    if (*(arr+index) == value)
        return index;
    return -1;
}
//改成递归试试。
int _Find(unsigned index, const int* const arr, const unsigned& length, const int& value){
    if (arr[index] == value)
        return index;
    if (arr == nullptr || length == 0||index==length)
        return -1;
    return _Find(index + 1, arr, length, value);
}
int _Find_Array(const int* const arr, const unsigned& length, const int& value){
    return _Find(0, arr, length, value);
}
int main(){
    int arr[10] = { 1, 2, 3 };
    std::cout << Find_Array(arr, 10, 1) << std::endl;
    std::cout<<_Find_Array(arr, 10, 10) << std::endl;
    system("pause");
    return 0;
}

打印容器示例：

#include<iostream>
#include <vector>
void Print(const std::vector<int>& ivec,const std::vector<int>::size_type& n){
    if (ivec.empty()||n<=0)
        return;
    Print(ivec, n - 1);
    std::cout << ivec.at(n - 1);
}
void Print_Vector(const std::vector<int>& ivec){
    Print(ivec, ivec.size());
}
int main(){
    std::vector<int> ivec{ 1, 2, 3, 4 };
    Print_Vector(ivec);
    std::cout << std::endl;
    system("pause");
    return 0;
}

打印链表示例：

#include <iostream>
class Node{
public:
    int data;
    Node* next;
    Node(int _data = 0) :data(_data), next(nullptr){}
};
using PNode = Node *;
//打印链表：
void Print_List(const Node* p){
    if (p == nullptr)
        return;
    while (p){
        std::cout << p->data << " ";
        p = p->next;
    }
}
//递归写法
void Print(const PNode p){
    if (p == nullptr)
        return;
    std::cout << p->data << " ";
    Print(p->next);
}
int main(){
    Node p1, p2, p3;
    p1.data = 1;
    p1.next = &p2;
    p2.data = 2;
    p2.next = &p3;
    p3.data = 3;
    p3.next = nullptr;
    Node *p = &p1;
    Print_List(p);
    Print(p);
}

总结：

1.递归的基本思想是分治。在第二个查找函数中，可能写成递归并不是那么好，而且递归理解起来也是比较费劲。但是把握了分治的基本思想还是可以接受的。查找函数中，分治是如下的：一个一个进行分，这也是属于分治。但是在输出函数中，分治却是这样的：输出n-1个数和第n个数，划分成两种。总之，要深刻把握住分治的内涵，切不可简单的认为递归只是函数调用自身。
2.多多揣摩代码，尽量自己动手实现一遍。
3.参考博文：戳我进去看原文
ps:下面应该还是递归和循环相关的内容。