递归和递归函数

使用.
– 变量 .
使用->
– 指针 ->

双链表
结点
数据自身
next – 下一个结点
prev – 上一个结点

链表翻转

==========================
递归和递推函数
main函数调用 foo函数
main函数 – 调用函数
foo函数 – 被调用函数

递归函数 – 函数自身调用自身
函数A 调用函数A

void love(int n){
if(n > 1){
love(n – 1);
}
printf(“love %d times\n”, n);
}
int main(void){
love(3);
return 0;
}
n = 3;

love(3){
if(n>1){
love(2);//1-1, yes
}
printf(“love 3 times\n”);//1-2,no
}

love(2){
if(n>1){
love(1);//2-1, yes
}
printf(“love 2 times\n”);//2-2, no
}

love(1){
if(n > 1){
love(0);//3-1, 不执行
}
printf(“love 1 times\n”);//3-2, 执行
}

printf(“love 1 times\n”);//3-2
printf(“love 2 times\n”);//2-2
printf(“love 3 times\n”);//1-2

逐层调用, 逐层返回

什么时候去使用递归函数
正要做的是就是正在做的事, 就可以使用递归
做得事情都是完全一样的, 参数不同而已
假设递归函数已经可以使用了 ☆
无限递归 – 死递归
特别注意终止条件 – 自身调用自身停不下来
递归到什么条件下就不再适用了, 终止条件

求和
sum = 1 + 2 + 3 + …
举例:
f(n) = 1 + 2 + 3 + (n-2) + (n-1) + n
f(n-1) = 1 + 2 + … + (n-2) + (n-1)
f(n-2) = 1 + 2 + … + (n-2)

f(n) = f(n-1) + n 
...
f(2) = f(1) + 2 
    f(1) = f(0) + 1 //不适用了
f(1) = 1 //适用

//该函数功能是计算前n个整数数据之和
int f(int n){
if(n == 1)
return 1;
return f(n-1) + n;
}

f(100) = f(99) + 100
f(99) = f(98) + 99
…
f(-100)= f(-101) + (-100)

sum += i;
sum = 1
sum = 1 + 2;
sum = 1 + 2 + 3;
sum = 1 + 2 + .. + n;

实现n的阶乘

n! = 1 * 2 * 3 * … * n fact(n)
(n-1)! = 1 * 2 * 3 * … * (n-1) fact(n-1)

n! = n * (n-1)!
fact(n) = n * fact(n-1)

1! = 1

recur.c

斐波那契数列 – fibonacci
第n个数等于前两个数据的和

1 1 2 3 5 8 13 21 34 55 89 144 ..

f(n) = f(n-1) + f(n-2)

vim fibo.c

1.递归函数
2.二级指针 –

修改一级指针 – 参数 – 二级指针

树
之前研究的都是 – 一对一的结构
现实存在很多一对多的情况 – 研究一对多的数据结构 – 树
树中的每个元素称为节点(node)
每个节点都有零个或者多个子节点
没有父结点的节点称为根节点,
每一个非根节点有且仅有一个父结点

根节点左侧的部分可以看做是一颗新的树, 这棵树就是属于根节点的左子树.
同样, 根节点右侧的部分就是其右子树

一个节点的子节点(子树)的数量称为节点的度
节点的层次 – 节点的层次从根节点开始定义, 根为第一层, 根的子节点为第二层, 依次向下分

有序二叉树
每个节点最多含有两个子树的数称为二叉树
一般来说, 当左子树不为空的时候, 左子树的元素值小于根节点, 当右子树不为空的时候, 右子树的
元素值大于根节点.
一句话, 不管站在哪个节点上, 左边总是小于右边