38. 递归和栈。

1.循环和递归。

1.1 求n! 9!=987...*1
1.2 求1+2+3+...+n

可以for循环实现，也可以递归实现。

递归：

1.一定有递归结束的条件。
2.求解的思路能拆分成个小的部分，每个小部分求解思路一致。
3.每个大的部分，是依赖小的部分的解决。

循环和递归的区别：
循环：
不容易理解(复杂的情况)，
高效一些
递归：比较容易理解，
低效一些。

循环能处理的，原则上递归也能处理；
但是递归能处理的问题，循环不一定能解决。 《递归论》

int sum = 1; 
for(int i=2; i<=10; i++){
    sum *=i;
}
// 递归实现。求n阶乘，需要借助n-1的阶乘。
// 每个步骤又依赖小的步骤。
int sum(int n) { //阶乘！
    if(n==1) return 1; // 递归结束条件    
    return n *sum(n-1);
}
int addAll(int n){ //累加
    if(n==1) return 1;
    return n + addAll(n-1);
}

2.汉诺塔问题，类似的还有八皇后问题。

每次只能挪动一个，从A柱移动到C柱，借助B柱子。
规则：每次挪动一个；大的必须在下面。

A柱有3个饼。
第一步：A的1挪到B，A的2挪动到C，此时A只剩下3.
第二步：把B的1挪动到A，C的2挪动到B，把A的1挪动到B，最后把A的3挪动到C。
第三步：把B的1挪回到A，把B的2挪动到C。
第四步：把A的1活动到C。完成汉诺塔。

A柱有9个饼，如何挪动？
从后往前推理，最后一步，把n直接A挪动到C。 然后n-1，再借助中间柱子，挪动到C。
n-1 从B 借助A 挪动到 C。
完毕。

n-1，从A 需要借助 C，挪动到B。 递归。

八皇后问题。

8*8 格子里面，摆放8个皇后，横竖斜，都不能有对手。
防止他们不能相互攻击，要怎么摆放。有多少种思路的求解。

3.数组实现栈

先进栈的后出去，后进栈的先出去。先进后出。
一种数据结构的思想。可以用数组，也可以用链表来存储。

#include <malloc.h>
#include <assert.h>

// ArrayStack.hpp 使用泛型。
template <class E>
class ArrayStack {
private:
    // 记录top角标，指向栈顶,栈顶元素的角标
    int top = -1; 
    E* array = NULL;
    int size = 10; // 栈的初始长度
    
public:
    ArrayStack();
    ~ArrayStack(); // 构造和析构方法
public:
    bool isEmpty(); // 栈是否为空
    E pop();   // 弹出栈顶元素
    E pick();  // 获取栈顶元素，但是不弹出来。
    void push(E e); // 元素压入栈中
private:    
    void growArray(); //扩容
};

template <class E>
ArrayStack<E>::ArrayStack() { //构造函数
    array = (E *)malloc(sizeof(E) *size);
}
template <class E>
ArrayStack<E>::~ArrayStack() { //析构函数
    delete[] array;
}

template <class E>
E ArrayStack<E>::pop() {
    assert(top >= 0); // 必须保证top>=0
    return array[top--];
}
template <class E>
bool ArrayStack<E>::isEmpty() { // 是否为空
    return top == -1;
}
template <class E>
E ArrayStack<E>::pick() {
    return array[top]; // 仅获取元素，不从集合中删除元素。
}
template <class E>
void ArrayStack<E>::push(E e) {
    if(top +1 == size) { // 是否有足够空间
        // 扩容。
        growArray(); 
    }
    array[++top] = e;
}
// 扩容
template <class E>
void ArrayStack<E>::growArray() {
    size += size >>1;
    array = (E *)realloc(array, size* sizeof(E)); //原基础上扩容，要传入总的大小。返回array首地址
}

ArrayStack<int> stack;
for(int i=0;i<10; i++){
    stack.push(i);
}
while(!stack.isEmpty()){ //栈非空，一直弹出。
    LOGE("%d", stack.pop());
}

4.链表实现栈

// LinkStack.hpp

#ifndef NDK_DAY37_AS_LINKSTACK_H
#define NDK_DAY37_AS_LINKSTACK_H

#include <iostream>
using namespace std;

// 节点类。
template <class E>
class Node {
public:
    Node* next;
    E value;
public:
    Node(E value, Node* next){
        this->value = value;
        this->next  = next;
    }
    ~Node(){
        LOGE("析构函数");
    }
};

//------------------------
template <class E>
class LinkStack {
private:
    Node<E> * head = NULL;   // 头节点,判断是否为空
    Node<E> * top = NULL;   // 栈顶节点, 降低插入的时间复杂度为O(1)。
    int index = -1; //当前索引：用于弹栈
    
public:
    ArrayStack();
    ~ArrayStack(); // 构造和析构方法
public:
    bool isEmpty(); // 栈是否为空
    E pop();   // 弹出栈顶元素
    E pick();  // 获取栈顶元素，但是不弹出来。
    void push(E e); // 元素压入栈中
private:
    Node<E> *node(int index);
};

template <class E>
LinkStack<E>::ArrayStack(){
    // 构造函数。
}

template <class E>
LinkStack<E>::~ArrayStack(){ // 西沟函数
    Node<E>* h = head;
    while(head){
        Node* next = h->next;
        delete h;
        head = next;
    }
    head = NULL;
}


template <class E>
void LinkStack<E>::push(E e){
    Node<E> *new_node = new Node<E>(e, NULL);
    if(top){ //top != NULL
        top->next = new_node;
    } else {
        head = new_node;
    }
    top = new_node;
    index++;
}

template <class E>
E LinkStack<E>::pop(){ 
    assert(index >= 0); // 不满足条件报错。
    
    //弹出 delete top，top指向前一个。 所有的都已经移除，top和head都设置为NULL。
    E value = top.value;
    if(head->next == NULL){ // 只剩一个头节点，此时index=0
        top = NULL;
        head = NULL;
    } else {        
        top = node(index -1); // 遍历，让top 指向上一个节点。
        delete top; // 删除top, 会触发析构
    }

    index--;
    return value; //返回弹出的值
}

// 根据index，得到相应的节点。
template <class E>
Node<E> *LinkStack<E>:: node(int index) {
    Node<E> *h = head;
    for(int i=0; i<index; i++){
        h = h->next();
    }
    return h;
}

#endif

// 在栈内存中，里面的方法也在栈内存。回去调用方法中 new对象的析构方法。
LinkStack<int> *stack = new LinkStack<int>();
stack->push(1); 
stack->push(2); 
stack->push(3); 
LOGE("%d", stack->pop());

TODO：使用双向链表优化，使插入和弹出都优化为O(1).