通过汉诺塔递归与非递归理解函数调用

C 程序的状态机模型 (语义，semantics)

• 状态 = 堆 + 栈
• 初始状态 = main 的第一条语句
• 迁移 = 执行一条简单语句
  • 任何 C 程序都可以改写成 “非复合语句” 的 C 代码

模型比较抽象，接下来把它落实到代码上以加深状态机模型的理解。

假如有三根柱子from、via、to，要求将n个盘子从from移动到to。

不了解汉诺塔游戏的，可以先玩一玩找到规律再来。

汉诺塔的解题思路：

1. from柱子的n-1个移动到via柱子
2. from柱子的1个移动到to柱子
3. via柱子的n-1个移动到to柱子

递归版代码

#include

void hanoi(int n, char from, char to, char via) {
	if(n == 1) {
		printf("%c -> %cn", from, to);
		return;
	} 
	hanoi(n-1, from, via, to);
	hanoi(1, from ,to ,via);
	hanoi(n-1, via, to, from);
}

int main(){
	int n; 
	scanf("%d",&n);
	hanoi(n,'A','B','C');
	return 0;
}

进一步拆解C 程序的状态机模型 (语义，semantics)

• 状态 = stack frame（栈帧）的列表 (每个 frame 有 PC) + 全局变量
• 初始状态 = main(argc, argv), 全局变量初始化
• 迁移 = 执行 top stack frame PC 的语句; PC++
  • 函数调用 = push frame (frame.PC = 入口)
  • 函数返回 = pop frame

然后落实到非递归版代码上，加深理解

#include
#include

typedef struct {
	int pc, n;
	char from, to, via;
} Frame;

//参数宏 ... 替换到 __VA_ARGS__ 
#define call(...) 
({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
#define ret() ({ top--; })
#define goto(loc) ({ f->pc = (loc) - 1; })

void hanoi(int n, char from, char to, char via) {
	Frame stk[64], *top = stk - 1;
	call(n, from, to, via);
	for(Frame *f; (f = top) >= stk; f->pc++) {
		switch(f->pc){
			case 0: 
				if(f->n == 1) {
					printf("%c -> %cn", f->from, f->to);
					goto(4);
				}
				break;
			case 1:
				call(f->n - 1, f->from, f->via, f->to); break;
			case 2:
				call(		1, f->from, f->to, f->via); break;
			case 3:
				call(f->n - 1, f->via, f->to, f->from); break;		
			case 4:
				ret(); break;
			default: assert(0);	
		}
	}
}

int main(){
	int n; 
	scanf("%d",&n);
	hanoi(n,'A','B','C');
	return 0;
}

POSIX是IEEE为要在各种UNIX操作系统上运行的软件而定义的一系列API标准的总称。

        POSIX是Unix的标准。有了这个规范，你就可以调用通用的API了，Linux提供的POSIX系统调用在Unix上也能执行，因此学习Linux的底层接口最好就是理解POSIX标准。加强了软件的移植性。

        Linux之所以能够成功，有很多因素，但是支持POSIX标准无疑是它能够快速发展的最重要的一个因素。

        Linux下对文件操作有两种方式：系统调用（system call）和库函数调用（Library functions）。

        系统调用是通向操作系统本身的接口，是面向底层硬件的。通过系统调用，可以使得用户态运行的进程与硬件设备(如CPU、磁盘、打印机等)进行交互，是操作系统留给应用程序的一个接口。

库函数（Library function）是把函数放到库里，供别人使用的一种方式。

库函数调用则是面向应用开发的，库函数可分为两类，

1. 一类是C语言标准规定的库函数，
2. 一类是编译器特定的库函数。

(由于版权原因，库函数的源代码一般是不可见的，但在头文件中你可以看到它对外的接口)。

glibc 是 Linux 下使用的开源的标准 C 库，它是 GNU 发布的 libc 库，即运行时库。这些基本函数都是被标准化了的，而且这些函数通常都是用汇编直接实现的。

glibc 为程序员提供丰富的 API（Application Programming Interface），这些API都是遵循POSIX标准的，API的函数名，返回值，参数类型等都必须按照POSIX标准来定义。

POSIX兼容也就指定这些接口函数兼容，但是并不管API具体如何实现。

如下图是Linux系统调用的大概流程。

当应用程序调用printf()函数时，printf函数会调用C库中的printf，继而调用C库中的write，C库最后调用内核的write()。

而另一些则不会使用系统调用，比如strlen, strcat, memcpy等。

printf函数执行过程中，程序运行状态切换如下：

用户态–>系统调用–>内核态–>返回用户态

printf函数、glibc库和系统调用在系统中关系图如下：

操作系统：设计与实现 (2022 春季学期) (jyywiki.cn)

posix是什么都不知道，还好意思说你懂Linux？ - 知乎 (zhihu.com)