本章无需前置知识，但最好了解如何存储树结构（可参考链表与邻接表）🙂

递归（入门）

我们先来看基础的递归写法结构：

void dfs(){
    if(condition()) return;	//结束条件
    dfs();
}

再来看看经典的求最大公因数gcd递归写法：

int gcd(int a, int b){
   return b ? gcd(b, a%b) : a; 
}

可见递归从形式上来看就是自己调用自己，而自己调用自己也存在着无法停下的风险，所以需要条件来结束递归。

而就形式上的了解是不可能掌握递归的。所以，接下来我们来讲递归的常用应用场景：树状结构的问题。

递归遍历树

先来个问题，面对一棵树，怎么遍历？

按照线性（比如数组）的遍历方法肯定是不行的（邻接表这么遍历也太掉逼格了）这里我们就可以使用递归，之后在图论中我们称此为dfs（深度优先搜索）。我们先来一个demo

demo

自己编的，不要在意

---

这里有棵树，每个节点上都有数值，定义每个节点的价值为节点数值乘上其深度（距离根节点的距离+1，根节点深度为1），树的价值是所有节点价值的和，求出给定树的价值。

---

input

6			//树有的节点数
1 2 3 4 5 6 //第i个数是节点i的数值
1 2 		//节点1 指向 节点2
2 3 
1 4 
2 5 
5 6 

output

61

code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n;
int h[N], ne[N], e[N], idx;
int v[N];

void init(){
    memset(h, -1, sizeof h);
    idx =-1;
}

void add(int x, int y){
    e[++ idx] = y, ne[idx] = h[x], h[x] = idx;
}

int ans;
void dfs(int u, int deep){
    ans += v[u]*deep;
    for(int i = h[u]; ~i; i = ne[i]){
        dfs(e[i], deep + 1);
    }
}

signed main(){
    freopen("in.in", "r", stdin);
    init();

    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> v[i];
    }
    for(int i = 1; i < n; i ++ ){
        int x, y;
        cin >> x >> y;
        add(x, y);
    }

    dfs(1, 1);

    cout << ans <<endl;
}

重点看一下这段代码：

void dfs(int u, int deep){
    //u为当前遍历的节点，deep为当前深度
    ans += v[u]*deep;
    for(int i = h[u]; ~i; i = ne[i]){
        dfs(e[i], deep + 1);	//遍历u所邻接的节点e[i]，树的深度加一
    }
}