递归技术

在计算机中,递归技术是和迭代技术齐名的技术,特别是在elixir和lisp编程语言中的递归相对于命令式的编程语言python,c语言等更是无处不在了.

乘法例子

我们小学的时候,经常计算的一个题目是b个a是多少,大家都知道答案是a*b,如果用python来写就是:

这样直接算的就是属于迭代技术,只是只有一次迭代,所以你没有见到for或者while等用于循环执行代码的python关键字.对于这个例子,我们可以认为在做两个数字相乘的结果,如上所说,我们可以看成是b个a相加,a+a+……a,那么我们就有如下的计算乘法的迭代代码:

所以,这很简单,对吧!

接下来转换思路,为了方便说明,我们假设a=5,b=4,那么a*b就是5*4,之前就说过可以把5*4看成4个5相加,5+5+5+5, 这个式子可以看成5+5*3,就相当于你让我计算5*4的结果,也就是4个5相加,但是我去算5+5*3,等同于我去算3个5相加,然后在和5相加,这样算下的结果和4个5是一样的,但是你不知道3个5相加是多少,于是你可以把3个5相加看成是5+5*2,可以你还是不知道2个5是多少,于是你可以把2个5看成是5+5*1,所以你就要去求1个5是多少了,很明显的1个5是5啊,因为就常识来说,1个任何数肯定是任何数,这也是最基本的情况了.递归的递到这里其实已经结束了,接下来的过程是属于归的过程了,你知道了1个5的结果是5,那么你就可以计算5+5*1,这个不就是2个5, 当时我们计算3个5相加的时候是依赖于2个5的,现在2个5的结果你已经知道了,所以2个5的结果加上5就是3个5的结果了, 3个5的结果你知道了,那么3个5的结果加上5就是4个5的结果了,你也就知道答案了.

5*4=5+5*3

   =5+5+5*2

   =5+5+5+5*1

b==1的情况是基本的情况,就表示计算1个a,那么函数就必须返回a

b!=1的情况:

我们规定mul(a,b)计算b个a,那么对应的mul(a,b-1)就是计算(b-1)个a,所以a+mul(a,b-1)就是a+(b-1)个a

所以,我们非常放心的在定义mul(a,b)的过程中调用自己而且调用形式是mul(a,b-1),这就是计算机编程中的递归,我们的规模是计算b个a,但是我不直接算,我们把任务委托给mul(a,b-1)先去计算(b-1)个a, 而且我们就认为它会给我们正确的结果,(有点唯心,是不是),也就说我们把问题的规模减小了,但是不能一直委托下去,不然就无限了,程序也就退不出来了,所以到达最基本的情况的时候,我们的基本情况可以认为b==1,也就是计算1个a,此时是必须可以直接知道结果的,由这个最基本的结果一路往回归.

https://pythontutor.com/ 网站可以查看具体的递归调用和返回过程,请读者自行动手体会和理解.

总结一下:某个问题如果可以拆解成规模更小的子问题,那么大概率可以使用递归来求解,设计递归算法有两个注意点,一个是确定基本情况,这种情况一般都可以直接求解,另一种情况是必须递归的情况,这种情况可以看成是某种递推关系,比如上面的例子中的mul(a,b),我们可以写出递推式子mul(a,b)=a+mul(a,b-1).

再举一个例子power

计算数字的次方,power(n,p)计算n的p次方,相信有上面的例子介绍,你很容易会写下如下的代码:

基本情况就是p==0的时候,直接返回1,递归情况就是如代码中的递推式

 

阶乘例子

计算n的阶乘,相信难不倒读者朋友

fact(n)=n*fact(n-1) 这就是求阶乘递推式,所以知道了递推式写递归函数并不难.

斐波那契数列

斐波那契相信大家都很熟悉了,数列的第一项为1,第二项为1,从第三项开始的每一项都是其前一项和前二项之和,所以第三项是2,第四项是3,第五项是5,……一次下去.

所以求斐波那契数列的第n项的代码如下:

所以如果调用fib(6),那么fib(6)=fib(5)+fib(4),所以会先调用fib(5), 进入fib(5)中,fib(5)=fib(4)+fib(3),所以会在此时调用fib(4), fib(4)=fib(3)+fib(2),所以fib(4)中会调用fib(3),在fib(3)中会发生fib(2)+fib(1), 所以先调用fib(2),这个调用会返回1,然后调用fib(1),这个调用会返回1, 所以fib(3)调用是会返回1+1的,也就是2,这只是调用链的一部分,完整的调用链读者可以自己画出来.画出来调用链就知道整个调用链有很多的重复计算.

所以,可以使用字典来保存计算过的子问题,代码如下:

没有基本情况了,只是求第n项的时候是先查找字典,如果字典有第n项的值,直接返回即可,如果没有,那么就通过递推公式去计算,算好后保存到字典中,最后返回

计算列表中所有元素的总和

这个恐怕是很多人编程开始时候都做过的.那么如何用递归的方法做呢?如果用递归思路来计算,那么递推式明显就是sum(L)=L[0]+sum(L[1:]), 因为我们规定sum(L)是表示L的所有元素的和,那么明显的sum(L[1:])就表示L[1:]中所有元素的和,所有也就有了前面的那个递推式:

在举一个例子,元素e是否在列表L中

写一个函数 def in_list(L, e) 如果e在列表L中,返回True,否则返回False.要求用递归思路来写.

解释直接看注释,下面的优化版本

请读者自行体会

扁平化列表

给定一个包含列表的列表,比如[[1,2], [3,4], [5], [6,7,8]].返回[1,2,3,4,5,6,7,8]

递归代码:

这应该没有什么好解释的.

 

再来一个例子,元素e是否在列表中

给定一个包含列表的列表,比如[[1,2], [3,4], [5], [6,7,8]],和一个元素3,查询3是否在列表中:def in_list_of_lists(L, e):

 

再来一个例子:反转列表

给定一个列表,反转列表中的元素

如果L的长度是1,反转之后还是本身,所以返回L,

递归情况是,提取最后一个元素放在首位,然后放心的调用reverse_list(L[0:-1]),它会处理L[0:-1]的所有元素的反转, 调用完成之后会返回反转好的L[0:-1], 最后[L[-1]]+反转好的L[0:-1]可以作为reverse_list(L)的返回值了.

继续反转列表

不过这个列表中的元素有列表,也有单个元素,比如整数等等:形如这样的列表[ [33,9,5], 8, 0, [2, 21, 6], 3,8,[0,0,9],3,[2],[1,-1],[4, 9,0] ],我们想要的效果是 [ [0,9,4], [-1,1],[2],3,[9,0,0],8,3,[6,21,2],0,8,[5,9,33] ],里面的元素如果是列表,那么这个元素也要反转,不管包多少层.

读者自己理解吧.

优化的写法

 

派楼梯

如果一个楼梯有n个台阶,每一次只能走1个台阶或者2个台阶,那么请打印到达第n台阶的所有的方案?

def climb_stairs(n) n表示爬到第n阶楼梯的所有方案,那么如何利用递归思路来解决问题呢?首先如果

n==1的时候,那么解决方案只有1种,就是跨一步,所以所有方案就是 [[1]];

n==2的时候,解决方案有2种, 第1种跨1步再跨1步,第2种跨2步, [ [1,1],[2] ]

n==3的时候呢?因为每一次只能是跨1步或者2步,所以n==3的方案可以从n==1走上来,就是在n==1的基础方案上跨2步,那么解决方案是[ [1,2] ];还有就是我们可以从n==2走上来,此时在n==2的基础方案上跨1步,那么解决方案就是 [ [1,1,1],[2,1] ],那么两种情况的总方案合并起来就是n==3时的爬楼梯方案 [ [1,2],[1,1,1],[2,1] ]

n==4的时候,可以从n==2的方案上跨2步和从n==3的方案上跨1步,总方案就是[ [1,1,2],[2,2] ] + [ [1,2,1],[1,1,1,1],[2,1,1] ]

……

 要想到达第n台阶,但是每次又只能是走1步或者2步所以就只能是从第n-2台阶或者是第n-1走上来,具体是从第n-2台阶的方案基础上走2步,或者是从第n-1台阶的方案上走1步

 (有人问过,为何到达第n台阶,只能从第n-2台阶或者第n-1台阶走上去,因为题目的要求就是每次只能走1步或者2步,你是不可能从第n-3台阶上只能选择走1步或者走2步的情况下(也就是说只能2选1的情况)走到第n台阶的,所以第n-4台阶等等就都不需要考虑了

 

代码如下:

不过有大量的重复计算,可以优化,请读者自行完成

解释一下:同样的道理,我们同样是分清基本情况和递归情况,在基本情况中只需要考虑如何走到第1台阶和第2台阶,后续的台阶是依赖于其前一个台阶和前二个台阶,所以我们代码中就放心的递归调用climb_stairs(n-2)和climb_stairs(n-1),它会返回子问题的方案,二第n台阶的方案基于这两个子问题,而这个问题较简单是直接合并两个子问题的方案就是整个问题的方案

 

 

 

 

 

 



拆分整数

定义一个函数count_partitions(n,m),n,m都是整数,要把n拆成不大于m的整数的组合,求这样的组合有多少个?

举个具体数字,比如n==6, m==4,那么符合条件的组合数量是9,具体是如下:

2+4=6

1+1+4=6

3+3=6

1+2+3=6

1+1+1+3=6

2+2+2=6

1+1+2+2=6

1+1+1+1+2=6

1+1+1+1+1+1=6

 

那么如何用递归的思路解决问题?递归的思路无非就是把问题拆分成一个个的子问题,并坚定的认为子问题能给你正确的结果,然后在看如何处理子问题返回的结果,也就是你要具体如何操作子问题的返回结果来搞定整个大问题. 至于如何拆解子问题,或者说是按照什么标准拆解子问题,有一个思路是通过参数,既然如此,那么对于这个问题,我们就可以这么思考:为了方便我们先假设n==6,m==4,把所有的组合数拆成2部分,包含有4的和没有包含4的,也就是count_partitions(6-4,4)和count_partitions(6,3), 包含有4的这一部分是count_partitions(2,4),其实就是在计算2的分割(因为这一部分已经确定了有一个4了,那自然是对于其余部分也就是6-4=2的分割了,2可以分割为1,1和2),所以count_partitions(2,4)是应该返回2的.没有包含4的部分是count_partitions(6,3),而且这一部分的返回结果是7,然后我们顶层的大问题其实就是这两个子问题的结果相加就是所求的组合数了.只是那那两个子问题继续调用的时候,它们也是按照包含xx的部分和不包含xx的部分来计算它们的结果的.

好了,那么基本情况是什么呢?当n==0的时候,可以认为在分割0,返回1,认为只有1种;因为递归过程种会n-m,所以n有可能小于0的,n<0,是负数,认为应该返回0; 还有就是m在递归过程种是一直减掉1的,认为m==0的时候,也应该返回0,因为没法用小于等于0的数去构建n.


求集合的所有子集

给定一个集合,比如[1,2,3],计算该集合的所有子集,返回[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]].函数原型定义为def combination(L)  #返回L的所有子集

 

请使用递归方法计算,针对这个问题,我们可以这样思考,首先把集合[1,2,3]拆分为1和[2,3],然后因为我们规定了combination(L)就是返回L的所有子集,那么很明显的combination(L[1:])就是返回[2,3]的所有子集(也就是[[], [3], [2], [2, 3]], 这些子集是不包含有元素1的)了, 然后我们把第一个元素1加入到combination(L[1:])返回的所有子集中,就变成了[ [1],[1,3],[1,2],[1,2,3] ],这些子集是包含有元素1的,然后把不包含元素1的子集和包含元素1的子集合并起来就是整个集合[1,2,3]的所有子集了.


求列表的全排列

全排列相比大家都很熟悉了,如果读者里有小学生或者中学生不知道全帕列的话,请参考维基百科.

此处稍微说一下, 假设求[1,2,3]列表的全排列,那么可以返回 [ [1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1] ],当然大列表里的6个元素的顺序可以任意的.

 

我们先使用一个迭代法(从下往上)来求出一个列表的全排列,后续在把它改成递归形式.

首先定义函数:用于把elem元素插入到列表L中的所有空隙中,具体如下所示,这个函数后面要用到.例如例子中的0插入到[1,2,3]列表的所有空隙中.

接下来是主函数:

稍微解释一下,如果L是空列表,直接返回[],如果有1个元素也是直接返回的,程序其实是至少有2个元素才会进入for循环开始不断迭代的,当L有2个元素的时候,假设L=[1,2], 那么此时prev=[ [1] ], 然后就进入for循环,针对2这个元素,遍历prev列表,把2插入到prev列表的所有的元素的空隙中,所以temp=[[2,1],[1,2]],把这个temp大列表中的所有元素累加到next列表中,因为prev只有一个元素,所以退出遍历prev的循环,此时让prev指向next,然后针对下一个元素如此往复……

其实就是针对L[i],prev是已经包含有L[0:i]中的元素的所有全排列了, 此时next清空,然后遍历prev大列表中的每个列表,在该列表的空隙中插入L[i]形成新的列表,把这样的列表全部放入到next中,当遍历完成prev列表后,让prev指向next,然后针对L[i+1]也是这么搞,解释的很烂,读者自己体会吧.

 

接下来,直接给出递归的版本吧(当然了,算法和上面的是一样的)

Insert_elem和迭代版本的一样,只是改成生成器函数了,permute也改成生成器函数了,代码中首先是基本情况,如果L的空列表,那么直接返回,如果非空,就是需要递归的情况了,在,首先获取L[1:]列表的所有的全排列,这一步是通过放心的递归调用permute(L[1:])来得到的, 然后遍历这个不包含有L[0]元素的全排列大列表(当然了这里全部都是生成器,不会真的需要内存来保存这个大列表,这里只是为了说明阐述,所以这样说)里的每一个元素,在每一个元素的所有空隙中插入L[0],形成新列表,把这个形成的新列表yield出去即可. 


背包问题 (可以用递归解决的经典问题)

给定两个长度都为N的数组weights和values,weights[i]和values[i]分别表示第i号物品的重量和价格, 给定一个正数W, 表示一个栽重为W的袋子,你装的物品不能超过这个重量, 返回你能装下的物品的最大的价值是多少?

相信编程初学者看到这种问题的话,大概率是一脸懵逼的.其实可以用最暴力的方式来思考,每一号物品都有挑选或者不挑选两种状态. 知道了这个,我们就可以规定一个函数process:

process(weights: list, values: list, i: int, j: int)来表示在剩余重量为j的情况下,从第i号物品开始到最后的第(n-1)号物品中进行选择(针对这些物品,每一号物品都有选或者不选两种情况),来达到最大的重量.


# 针对每号物品都有选或者不选,

# process函数表示在剩余重量为j的情况下第i个物品开始通过某种策略挑选物品,以使得价值达到最大



def process(weights: list, values: list, i: int, j: int):

    if i == len(weights): # 这里是基本情况了,表示从第n号物品开始选择,那肯定是返回0

        return 0

    elif j >= weights[i]: # j >= weights[i]表示剩余重量大于等于weights[i],所以有权利挑选物品i,在这种情况下有不选和选两种状态

        return max(process(weights,values,i+1,j), process(weights, values,i+1, j-weights[i]) + values[i]) # process(weights,values,i+1,j)这是不选物品i, 所以就是说在背包剩余重量为j的情况下,从第(i+1)号物品里去选,能达到的最大价值; process(weights, values,i+1, j-weights[i])这是表示挑选了物品i, 所以只能在剩余重量为(j-weights[i])的情况下,从第(i+1)号物品开始挑选,能达到的最大价值; 然后两个子问题的最大价值搞定了,最大的问题不就是比较一下哪个价值大,返回那个价值较大的即可.(大的就是在整合子问题的答案)

    elif j < weights[i]: # 无法挑选物品i

        return process(weights, values, i+1, j) #


weights=[2,1,3,2]

values= [3,2,4,2]

W=5

process(weights, values, 0, W)  # 刚开始背包的剩余重量就是W了,从第0号物品开始



因为递归解法涉及了一些不太直观的思维方式，特别是**「自顶向下」的思考方式**。让我们一步步拆解，看看如何培养这种递归思维。

为什么递归难写？

  1. 不习惯「自顶向下」的思维

    • 你可能更习惯迭代式的写法，比如用 for 或 while 循环，而递归要求你假设子问题已经解决了，这不太直观。
    • 递归代码本质上是分解问题、让递归函数去处理剩下的部分，这一点需要一些练习才能掌握。

  2. 递归终止条件不好把握

    • 很多人写递归时，容易忘记设定递归终止条件，导致无限递归或错误结果。
    • 在 process() 这个代码里，i == len(weights) 就是递归的出口，这是停止向下拆分问题的关键。

  3. 「选与不选」的决策难以转换成代码

    • 在 0-1 背包问题中，每个物品有**「选」或「不选」两种状态，这种分叉思维**不太好直接写成代码。
    • 但如果你把递归当作**「列出所有可能性」的方式**，再用 max() 选最优解，就会容易很多。

如何训练自己能写出这样的递归代码？

下面是一个方法，你可以试着跟着步骤写出来：

1. 明确递归函数的含义

在 process(weights, values, i, j) 里，i 和 j 分别表示：

  • i 代表当前考虑的物品（索引）
  • j 代表当前剩余背包容量

这个函数的目标是：
「从第 i 个物品开始，背包剩余容量为 j 时，能获得的最大价值。」

2. 找到递归终止条件

如果 i == len(weights)（没有物品可选了），直接返回 0：

python
if i == len(weights):
    return 0

这保证了递归最终会停止。

3. 找到「选」或「不选」的决策

递归的核心在于：

  • 不选当前物品 → 直接看下一个物品，容量不变。
  • 选当前物品（前提是能装得下） → 增加当前物品的价值，容量减少。

代码实现：

python
elif j >= weights[i]:  
    return max(
        process(weights, values, i + 1, j),  # 不选当前物品
        process(weights, values, i + 1, j - weights[i]) + values[i]  # 选当前物品
    )
  • 不选：直接递归到 i+1，容量 j 不变。
  • 选：价值 values[i] 加上 剩余空间的最优解。

4. 处理「装不下」的情况

如果当前物品太重，背包已经装不下了，那只能跳过：

python
elif j < weights[i]:  
    return process(weights, values, i + 1, j)

这里没有 max()，因为我们根本没法选它。

用伪代码练习递归思维

如果你想练习自己写出来，不妨试试按照下面的伪代码框架：

  1. 定义递归函数
    python
    def my_function(参数1, 参数2, ...):
  2. 找到终止条件
    python
    if 终止条件:
    return 结果
  3. 思考「选或不选」
    python
    elif 能选:
    return max(不选的情况, 选的情况)
  4. 处理「不能选」的情况
    python
    else:
    return 不能选时的递归调用

你可以试试自己写

如果你要自己写出 process(weights, values, 0, W) 这样的代码，试着不看原代码，自己写一个类似的递归函数，看看能不能写出来！比如：

练习题：

你有一个数组 nums，你要找出所有子集的和，最大是多少？
函数定义：

python
def subset_max_sum(nums, i, current_sum):

试着自己写写看！💡

如果你写出来了但不确定对不对，可以贴过来，我帮你看看！ 🚀


递归用于排序:快速排序

我们前面的递归的例子的规模假设是n,子问题一般都是n-1这种线性的,比如power例子中,power(n,p)表示n的p次方,我们先求出power(n,p-1),这个问题的规模是p,我们求其p-1; 阶乘例子中,fact(n)表示求n的阶乘,我们先求(n-1)的阶乘,等等.接下来说一个类似于对半切分的递归.

现在将一个三路快速排序的算法,不过在那之前先看一个荷兰国旗问题.

给你一个数组arr和一个基准值pivot,请将数组中小于基准值pivot的元素放在数组的左边,等于基准值pivot的元素放在数组的中间,大于基准值pivot的元素放在数组的右边?  def partition(arr, L, R)  (为了和后面的整体代码统一, pivot直接设定为数组的最右边元素,不体现在partition函数中的参数中了, L和R用来限定数组中参与运算的边界)

这个问题的解决方案和荷兰国旗的解决方案一样.

pivot设定为基准值,大致过程是这样的,遍历每一个数组元素,如果小于基准值,当前被遍历的元素arr[i]被交换到数组左边,如果大于基准值,当前被遍历的元素arr[i]被交换到数组右边,如果等于基准值,直接遍历下一个元素,其中less和more用来限定数组的左右区域的,随着代码的运行,less往右边移动,扩大数组的左区域,more往左边移动,扩大数组的右区域.具体魔鬼细节,读者可以跟踪代码的执行过程.

 

完成好这个之后,快速排序其实就很简单了

注释解释的很清晰了,基本情况很简单就是L>=R,递归情况里面要说下,一上来随机化基准值就是如同注释说的,不解释了,紧接着就对数组做partition做三分区,一次性把一批数据排好序,然后递归去排序左边,递归去排序右边.我们整个写代码的最顶层核心其实就三行代码:left,right=partition(arr,L,R) quick_sort(arr,L,left-1) quick_sort(arr,right+1,R)

这个顶层就相当于在做决策,是吧,1分区(并且搞定一批数据),2递归排序数组左边(调用完成后,放心的认为arr[L:left]一定会有序),3递归排序数组右边(调用完成后,放心的认为arr[right+1:R+1]一定有序),就是在整合子问题返回回来的结果(虽然这个例子的两个递归调用函数返回的是None,主要是因为我们是快速排序,如果是归并排序,递归之后回来是要做合并的,读者可以自己去写合并排序).

 

在啰嗦一句,从整体上,我们规定quick_sort(arr,L,R)会把数组arr[L:R+1]排好序,那么很明显的quick_sort(arr,L,left-1)就会把数组arr[L:left]排好序,也就是左边排好序, quick_sort(arr,right+1,R)就会把数组arr[right+1:R+1]排好序,也就是右边排好序.(记住:python的切片是[ ) 左开右闭的)


评论

发表评论

此博客中的热门博文

OAuth 2教程

图片
原文： http://tutorials.jenkov.com/oauth2/index.html OAuth 2.0是一种开放式 授权 协议，该协议使得应用程序可以访问彼此的数据。例如：一个游戏应用可以访问Facebook中的用户数据，或者基于位置的应用程序可以访问Foursquare应用程序的用户数据（ user data ）等。 OAuth 2.0被用于通过应用程序共享数据的示例如上图。 首先用户进入游戏的web应用，该应用要求用户通过Facebook账户登录，并定向到Facebook的登录界面，用户登录Facebook后，会重定向到之前的游戏应用。此时该应用就访问到了用户在Facebook的用户数据以及授权信息，并代表用户在Facebook中调用功能（例如发布状态更新）。 OAuth 2.0 用例 OAuth 2.0既可以用于在某个应用内访问其它应用的用户信息（比如上例中的游戏应用），又可以提供用户授权服务供其它应用调用（比如上例中的Facebook）。 OAuth 2.0是OAuth 1.0的替代，因为OAuth 1.0太复杂了，比如OAuth 1.0要求使用证书等。OAuth 2.0更加简单，不要求使用证书，仅使用SSL/TLS。 OAuth 2.0 规范 这个教程的目的是提供一个OAuth 2.0协议的概览以帮助理解，而不是涵盖此协议的所有细节。 如果你计划实现一个OAuth 2.0协议，最好是去阅读规范的详细内容，规范的地址：http://tools.ietf.org/html/draft-ietf-oauth-v2-23 OAuth 2.0 概述 在之前的介绍中我们提到，OAuth 2.0是一个开放标准，其允许某个应用程序访问其它应用程序的用户授权的数据。现在我们来介绍这个协议是如何工作的，以及规范中提到的各种概念。 OAuth 2.0 提供了不同的方式使得客户端应用获得权限去访问存储在资源服务器中的资源。现在介绍其中最安全和最常用的使用方式： 一个web应用请求访问另一个web应用 的资源。 下面的示例图描述了整个认证过程： 首先，用户访问客户端Web应用程序，在这个应用程序里有“通过Facebook登录”（或谷歌或Twitter等其他系统）的按钮。 第二步，当用户点击这个按...
阅读全文

rootfs，linux目录结构，（第3天）

1：Linux根文件系统（root filesystem）的概念 linux内核启动的时候，会创建根文件系统（root filesystem 简称rootfs），根文件系统（rootfs）是被包含在根目录所在的分区下的文件系统，并且当系统启动的时候，所有其他的文件系统会被挂载到该根文件系统下。 分区是硬盘上逻辑独立的部分。文件系统是用于在计算机系统上组织文件的目录（也称为目录树）的层次结构。在Linux和其他类似Unix的操作系统上，目录以根目录开头，其中包含一系列子目录，每个子目录又包含进一步的子目录等。这个定义的一个变体是位于单个分区或磁盘上的目录（即，目录树）的整个层次结构的部分。 根文件系统（rootfs）的确切内容将根据计算机而有所不同，但是它们将包括引导系统所必需的文件，并使其达到可以安装其他文件系统的状态以及用于修复系统损坏的工具和从备份中恢复丢失的文件的状态。根文件系统（rootfs）的内容包括根目录以及包含/boot，/dev， /etc，/bin，/sbin和/tmp（用于临时文件）的子目录和文件的最小集合。 当系统以单用户模式启动时，只有根文件系统（rootfs）可用。单用户模式是引导受损系统的一种方法，该模式功能非常有限，可以进行维修。修复完成后，位于不同分区或不同介质上的其他文件系统可以挂载到（即附加到）根文件系统上，以恢复完整的系统功能。其中挂载其他文件系统的目录称为挂载点。 根文件系统通常应该很小，因为它包含关键文件和一个小的，不频繁修改的文件系统有更好的机会不会被破坏。损坏的根文件系统通常意味着系统从HDD不能引导（即不可启动），并且必须通过特殊方式（例如，从启动软盘）引导。 文件系统可以挂载在目录树中的任意位置；它不一定需要挂载在根文件系统上。例如，将A文件系统挂载在根文件系统上的挂载点是可能的（而且很常见），并且另外一个文件系统B挂载在A文件系统上的某个挂载点上。 2：FHS LSB, FHS: (FileSystem Heirache Standard)：定义了Linux操作系统中的主要目录及目录内容。在大多数情况下，它是一个传统BSD文件系统层次结构的形式化与扩充。 FHS由Linux基金会维护，这是一个由主要软件或硬件供应商组成的非营利组织，例如HP、Red Hat、IBM、和Dell。 ...
阅读全文