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).
网友评论