一.递归
(一)介绍
1 .递归是指过程或函数在其定义或说明中直接或间接调用自身的方法。 通常,将一个大而复杂的问题层层变换成与原问题相似的小规模问题进行求解。 递归策略可以用很少的程序描述求解问题过程中所需的迭代计算,大大减少程序的代码量。 递归的能力在于用有限的语句定义对象的无限集合。 通常,递归需要边界条件、递归前进段和递归返回段。
2 .递归的两个重点:递归边界和递归公式
3 .递归优点:将大型复杂问题转换为有效问题,减少代码量
4 .递归的缺点:递归到一定程度后,会发生堆栈溢出,反复计算的次数多,效率低
(二)例
1 .斐波那契数列: f(n )=f(n-1 ) f(n-2 ) (n2 ) f )0)=1; f(1)=1;
程序:
intf(intI ) while(I==0||I==1) /递归边界({return 1; }returnf(I-1 ) f ) I-2; //递归公式}测试用例:
void FibonacciTest () {int n=9; for(intI=0; i n; I ) inta=f(I ); STD:3360cout'I '个' '斐波那契数列的值为' a endl; }输出:
复杂性:
时间: o(2^n )空间: o(2^n ) )。
2 .阶乘: f(n ) ) (n-1 )…)1)简化为f(0)=1)。 f(n )=f(n-1 ) (n ) n ) ) )。
程序:
intfactorial(intn ) while (n==0) /递归边界{return 1; }返回因子(n-1 ) *n; //递归公式}测试用例:
void FactorialTest () {int n=5; std:cout '阶乘' n '的值:“factorial(n ) endl; }输出:
复杂性:
时间: o(2^n )空间: o(2^n ) )。
二.反复
(一)介绍
迭代:利用变量的原始值来估计变量的新值。 如果递归是自己呼叫自己的话,反复就是a不断地呼叫b。
三.循环
(一)介绍
如果满足条件,则重复执行相同的代码
四.遍历
(一)介绍
按照一定的规则访问树结构中的每个节点,每个节点只能访问一次。