【研究空间复用及函数调用问题】

1.空间复用问题

案例1

我们先来看一个代码：

void F1()
{int a = 10;printf("%p\n", &a);
}
void F2()
{int b = 10;printf("%p\n", &b);
}
int main()
{F1();F2();return 0;
}

F1和F2函数的操作基本一样，你说它们所开辟的空间的地址是同一块吗？
或者说，a和b的地址是一样的吗？

结果是：一样的。为什么呢？

我们知道调用函数需要给函数开辟栈帧，也就是开辟空间，而栈帧是在堆区开辟的
当函数使用完后，该函数栈帧就要销毁。
但不是真正意义上的销毁，而是把使用该空间的权限还给操作系统，这片区域不再受你操控。

所以我们在调用F1()函数时，操作系统先给F1()开辟栈帧，给变量a分配内存。然后当F1()函数结束时，该空间又被操作系统收回
接着又调用F2()函数，操作系统又将刚刚收回的空间又分配给F2()函数。
所以F1函数和F2函数使用的空间地址是一样的，变量a和变量b的地址也就是一样的。

案例2

这是一个阶乘递归的代码

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}
int main()
{long long n;Fac(n);return 0;
}

请问它的空间复杂度和时间复杂度是多少呢？

函数Fac每次调用都会返回Fac(n-1)*n,直到N==0时才返回1.
也就是递归了n次，所以时间复杂度为O(n).
而空间复杂度呢？
因为Fac函数每次调用自己都会开辟一个函数栈帧，调用了n次，所以开辟了n个空间。
所以空间复杂度也是O(n).

那想一下，Fac(n)与Fac(n-1)与Fac(n-2)…等函数的空间地址是同一块空间吗？

综合上面的案例我们应该判断它们不是同一块空间的。

为什么呢？
上面的案例是F1函数调用完,结束后，再调用的F2函数
而阶乘递归是属于嵌套调用，每个函数都还没完全结束就又调用另一个函数了，所以它们开辟的空间肯定不一样，它们各自使用的空间都没有被操作系统收回过，怎么可能有其他函数又去占用这块空间呢。

而对案例修改一下，也可以让F1和F2函数的地址不一样，也就是在F1函数的内部去调用函数F2，这样它们的空间就不会重复了。

如下所示：

void F1()
{int a = 10;printf("%p\n", &a);F2（）；
}
void F2()
{int b = 10;printf("%p\n", &b);
}
int main()
{F1();return 0;
}

2.函数调用过程不清晰问题

案例3

这是一个斐波那契契递归Fib

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
int main()
{long long n;Fib(n);return 0;
}

你知道这个递归Fib函数的空间复杂度和时间复杂度吗？
Fib(n)函数每次返回两个函数Fib(n-1)+Fib(n-2).直到n<3时返回1.
也就是Fib函数每次调用都会又调用两个函数，而这个两个函数相当于又调用4个函数依次类推…最后应该调用2^n次
所以时间复杂度为O(2^n).

那空间复杂度呢？空间复杂度是多少呢？
有的人可能想呀，它不是相当于调用了2 ^ n次嘛，那不就是申请了2 ^ n个空间吗。真的是这样吗？

可能现在还有很多人没有搞清楚函数是怎么调用的，递归是怎么调用的。
有的人可能想是Fib(n)调用Fib(n-1)和Fib(n-2),然后操作系统就给Fib(n-1)和Fib(n-2)分配栈帧了，但其实不是。
函数的调用只有完全调用完才能去执行下一步。
调用Fib(n-1)后，其实会继续往下面调用Fib(n-2),然后再往下调用Fib(n-3)直到调用到Fib(2),Fib(2)返回1后，Fib(2)也就结束，函数栈帧销毁，回到F(3)，F(3)这时才开始调用F(1),F(1)返回1，F(1)的栈帧销毁，返回F(3)，F(2)又开始调用了。依次类推

Fib(2)返回后，操作系统是不是就将它的空间回收了，然后又调用了Fib（1）所以Fib(1)开辟的空间就是刚刚操作系统收回的空间呀。
其实就是左边Fib(2)和右边F(1)用的是同一块空间。依次类推，Fib(4)返回后，空间被收回，然后操作系统又将空间分配给右边的Fib(3)使用。所以大体上左边和右边是共用一块空间，而左边是调用了n个空间，所以最后的空间大小是O(n).

3.总结

这三个个案例本质上就是要搞清楚函数栈帧是如何创建的以及如何销毁的。

搞清楚函数是如何调用的，调用前操作系统要给函数分配栈帧，调用函数结束后，操作系统要将栈帧收回。
如果对函数栈帧方面有兴趣的可以阅读一下博主的《细谈函数栈帧的创建与销毁》。
还有我们可以发现：
时间是一去不复返的，不可再重复利用。
而空间是可以重复利用的。所以我们要特别重视算法的时间效率。