编程题:有n步台阶,一次只能上1步或2步,共有多少种走法?
递归

循环迭代

核心代码
- 递归
- TestStep.java
public class TestStep { /** * 实现f(n):求n步台阶,一共有几种走法 * * @param n * @return */ public int f(int n) { if (n < 1) { throw new IllegalArgumentException(n + "不能小于1"); } if (n == 1 || n == 2) { return n; } return f(n - 2) + f(n - 1); } }- TestStepTest.java
public class TestStepTest { @Test public void test() { System.out.println(new TestStep().f(1)); System.out.println(new TestStep().f(2)); System.out.println(new TestStep().f(3)); System.out.println(new TestStep().f(4)); System.out.println(new TestStep().f(5)); } @Test public void testCostTime() { long start = System.currentTimeMillis(); System.out.println(new TestStep().f(40));//165580141 long end = System.currentTimeMillis(); System.out.println(end - start);//642 ms } } - 迭代
- TestStep2.java
public class TestStep2 { /** * 实现f(n):求n步台阶,一共有几种走法 * * @param n * @return */ public int loop(int n) { if (n < 1) { throw new IllegalArgumentException(n + "不能小于1"); } if (n == 1 || n == 2) { return n; } int one = 2;//初始化为走到第二级台阶的走法 int two = 1;//初始化为走到第一级台阶的走法 int sum = 0; for (int i = 3; i <= n; i++) { //最后跨2步+最后跨1步的走法 sum = two + one; two = one; one = sum; } return sum; } }- TestStep2Test.java
public class TestStep2Test { @Test public void test() { System.out.println(new TestStep2().loop(1)); System.out.println(new TestStep2().loop(2)); System.out.println(new TestStep2().loop(3)); System.out.println(new TestStep2().loop(4)); System.out.println(new TestStep2().loop(5)); } @Test public void testCostTime() { long start = System.currentTimeMillis(); System.out.println(new TestStep2().loop(40));//165580141 long end = System.currentTimeMillis(); System.out.println(end - start);//2 ms } }
小结
方法调用自身称为递归,利用变量的原值推出新值称为迭代。
- 递归
- 优点:大问题转化为小问题,可以减少代码量,同时代码精简,可读性好;
- 缺点:递归调用浪费了空间,而且递归太深容易造成堆栈的溢出。
- 迭代
- 优点:代码运行效率好,因为时间只因循环次数增加而增加,而且没有额外的空间开销;
- 缺点:代码不如递归简洁,可读性好
源码地址
彩蛋
- 1.通过debug观察递归的堆栈信息

FEATURED TAGS
Cursor
AI
蝇量模式
责任链模式
工厂设计模式
观察者设计模式
每日一个设计模式
Spring中的设计模式
策略设计模式
设计模式原则
设计模式分类
Redis数据类型及应用
分布式锁
spring循环依赖
SpringAop
工一影单
书单
AQS
LockSupport
两数之和
字节跳动
leetcode
58同城
经典书籍
深入理解Java虚拟机
OpenJDK
Java基础
GitHub的骚操作
彩蛋
JDK
JVM性能分析工具
JVM监控
CPU占用过高解决思路
Linux常用命令
线上故障分析
G1垃圾收集器
垃圾收集器生产配置
默认的垃圾收集器
垃圾收集器
GC垃圾回收算法
OOM
虚引用
弱引用
软引用
强引用
Java的四大引用
jvm常用基本配置参数
JVM参数配置
JVM系统默认值
JVM调优
GC Roots
JVM垃圾回收
常见的垃圾回收算法
GC的作用域
JVM内存结构
ThreadPoolExecutor
线程池
阻塞队列
Semaphore
CyclicBarrier
CountDownLatch
自旋锁
Java锁
线程安全
ArrayList
原子更新
原子引用
ABA
AtomicInteger
CAS
高并发
多线程
juc
数据库连接工具
程序员简历
activeMQ
异步
消息队列
购物车
京东
分布式系统
单点登陆
集群
zookeeper
搜素引擎
solr
es
IO
数据结构
Redis
算法
GC
JVM
索引
MySQL
Redis持久化
git
Centos
服务类命令
Linux
字段不一致
MyBatis
工作流程
原理
post请求乱码
SpringMVC
传播属性
隔离级别
数据库事务
笔记
大数据
前端
Java
Bean作用域
Spring
JavaEE
Java变量
循环迭代
递归
循环与迭代
方法参数传递
类的实例化
类的初始化
设计模式
自增变量
面试题
JavaSE
安装教程
教程