函数调用栈和递归函数分析以及尾递归、缓冲区溢出的讲解 |
您所在的位置：网站首页 › 递归函数中必须出现return吗 › 函数调用栈和递归函数分析以及尾递归、缓冲区溢出的讲解 |
函数调用栈和递归函数分析以及尾递归、缓冲区溢出的讲解
|
知乎上有大神曾经说递归有时候更像去查字典，我们一开始想要知道这句话什么意思，里面有词语不认识，查字典，字典的解释又有新的我们不认识的词语，然后一直查找，直到我们弄懂了，我们开始回去理解上一层词语的意思，不断往上，直到最后我们理解了最初的那句话的意思。 查字典：调用栈中的递归函数的一个个返回结果 回去理解：利用一个个返回结果进行后续函数执行（理解）！ 以下代码理解栈：
/*!
* \file main.cpp
* \date 2018/12/26 20:42
*
* \author wangjinju
* Contact: [email protected]
*
* \brief 仅用递归函数和栈操作逆序一个栈
*
* TODO: long description
*
* \note
*/
#include
#include
#include
using namespace std;
//将栈stack的栈底元素返回并移除
template
T getAndRemoveLastEle(stack& s)
{
T result = s.top();
s.pop();
if (s.empty())
return result;
else
{
T last = getAndRemoveLastEle(s);
s.push(result);
return last;
}
}
//逆序一个栈
template
void reverse(stack& s)
{
if (s.empty())
return;
else
{
auto last = getAndRemoveLastEle(s);
reverse(s);
s.push(last);
}
}
int main()
{
vector v = { 0,1,2,3 };
stack s;
for (auto item : v)
s.push(item);
reverse(s);
for (; !s.empty();)
{
cout n)?(int)n:fib(n-1)+fib(n-2);
}
2.线性递归版：改进 为什么会改进？因为将每次计算的结果存了起来，不用重复计算了 int fib(int n, int &prev)//prev辅助变量记录前一项，复杂度O(n) { if(n == 0) { prev = 1; return 0; } else { int prevPrev; prev = fib(n-1,prevPrev);//递归计算前两项 return prevPrev+prev; } }3.动态规划版（循环问题用while往往起到意想不到的效果）：借助少量的辅助空间，记录子问题的解答 动态规划的思想： 把原始问题划分为一系列子问题求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时到时直接存取，不重复计算，节省计算时间自底向上地计算 int fibI(int n) //O(n) { int f=1,g=0; //初始化fib(1)=1,fib(0)=0 while(0 < n--) { int temp=g; g+=f; f=temp; } return g; } 尾递归的优点来源：https://blog.csdn.net/zcyzsy/article/details/77151709 普通递归需要压栈和出栈，时间空间消耗大；尾递归则没有（可以通过编译器优化）； 解释： 如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。 原理： 当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。 以尾递归方式实现阶乘函数的实现： int facttail(int n, int res) { if (n < 0) return 0; else if(n == 0) return 1; else if(n == 1) return res; else return facttail(n - 1, n *res); }res（初始化为1）维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而，在每次递归调用中，令res=n*res并且n=n－1。继续递归调用，直到n=1，这满足结束条件，此时直接返回res即可。 其实最精髓就是 通过参数传递结果，达到不压栈的目的 缓冲区溢出（程序在内存中的组织）堆：地址增长（有 8MB 的大小限制，一般用来保存局部变量） 栈：地址减小（动态的内存分配会在这里处理，例如 malloc(), calloc(), new() 等） 然后是数据，指的是静态分配的数据，比如说全局变量，静态变量，常量字符串。最后是共享库等可执行的机器指令，这一部分是只读的。 可以见到，栈在最上面，也就是说，栈再往上就是另一个程序的内存范围了，这种时候我们就可以通过这种方式修改内存的其他部分了。 
比如： typedef struct { int a[2]; double d; } struct_t; double fun(int i) { volatile struct_t s; s.d = 3.14; s.a[i] = 1073741824; // 可能会越界 return s.d; }不同的 i 可能的执行结果是： fun(0) -> 3.14fun(1) -> 3.14fun(2) -> 3.1399998664856fun(3) -> 2.00000061035156fun(4) -> 3.14fun(6) -> Segmentation fault之所以会产生这种错误，是因为访问内存的时候跨过了数组本身的界限修改了 d 的值。你没看错，这是个大问题！如果不检查输入字符串的长度，就很容易出现这种问题，尤其是针对在栈上有界限的字符数组。 在 Unix 中，gets() 函数的实现是这样的： // 从 stdin 中获取输入 char *gets(char *dest) { int c = getchar(); char *p = dest; while (c != EOF && c != '\n') { *p++ = c; c = getchar(); } *p = '\0'; return dest; }可以看到并没有去检测最多能读入多少字符（于是很容易出问题），类似的情况还在 strcpy, strcat, scanf, fscanf, sscanf 中出现。比如说 void echo() { char buf[4]; // 太小 gets(buf); puts(buf); } void call_echo() { echo(); }我们来测试一下这个函数，可能的结果是： unix> ./echodemo Input: 012345678901234567890123 Output: 012345678901234567890123 unix> ./echodemo Input: 0123456789012345678901234 Segmentation Fault为什么明明在 echo() 中声明 buf 为 4 个 char，居然一开始输入这么多都没问题？我们到汇编代码里去看看： 00000000004006cf : 4006cf: 48 83 ec 18 sub $0x18, %rsp 4006d3: 48 89 e7 mov %rsp, %rdi 4006d6: e8 a5 ff ff ff callq 400680 4006db: 48 89 e7 mov %rsp, %rdi 4006de: e8 3d fe ff ff callq 400520 4006e3: 48 83 c4 18 add $0x18, %rsp 4006e7: c3 retq # call_echo 部分 4006e8: 48 83 ec 08 sub $0x8, %rsp 4006ec: b8 00 00 00 00 mov $0x0, %eax 4006f1: e8 d9 ff ff ff callq 4006cf 4006f6: 48 83 c4 08 add $0x8, %rsp 4006fa: c3 retq我们看 4006cf 这一行，可以发现实际上给 %rsp 分配了 0x18 的空间，所以可以容纳不止 4 个 char。 在调用 gets 函数之前（第 4006d6 行），内存中栈帧示意图为： 结合上面代码可以看到，call_echo 栈帧中保存着调用之前执行指令的地址 4006f6，用于返回之后继续执行。我们输入字符串 01234567890123456789012 之后，栈帧中缓冲区被填充，如下： 虽然缓冲区溢出了，但是并没有损害当前的状态，程序还是可以继续运行（也就是没有出现段错误），但是如果再多一点的话，也就是输入 0123456789012345678901234，内存中的情况是这样的： 就把返回地址给覆盖掉了，当 echo 执行完成要回到 call_echo 函数时，就跳转到 0x400034 这个内容未知的地址中了。也就是说，通过缓冲区溢出，我们可以在程序返回时跳转到任何我们想要跳转到的地方！攻击者可以利用这种方式来执行恶意代码！ 那么我们现在来看看，怎么处理缓冲区溢出攻击，有几种方式： 好好写代码，尽量不让缓冲区异常程序容易出问题，那么提供系统层级的保护编译器也可以来个认证(stack canaries)第一种，避免缓冲区溢出，我们用更安全的方法，如：fgets, strncpy 等等。 第二种，栈的位置不确定，让缓冲区溢出没办法影响到，并且每次位置都不一样，就不怕被暴力破解。并且也可以把一段内存标记为只读，那么就避免因为缓冲区溢出而导致的重写。 第三种，使用认证机制(Stack Canaries)。简单来说，就是在超出缓冲区的位置加一个特殊的值，如果发现这个值变化了，那么就知道出问题了。 但是，除了缓冲区溢出，还有另一种攻击的方式，称为返回导向编程[4]。可以利用修改已有的代码，来绕过系统和编译器的保护机制，攻击者控制堆栈调用以劫持程序控制流并执行针对性的机器语言指令序列（称为Gadgets）。每一段 gadget 通常结束于 return 指令，并位于共享库代码中的子程序。系列调用这些代码，攻击者可以在拥有更简单攻击防范的程序内执行任意操作。 具体利用缓冲区进行攻击的例子，会在【读厚 CSAPP】III Attack Lab 中进行讲解，这里不再赘述。 |
【本文地址】
今日新闻 |
推荐新闻 |