第一季：5递归与迭代【Java面试题】

第一季：5递归与迭代【Java面试题】

• ​​前言​​
• ​​推荐​​
• ​​第一季：5递归与迭代​​

• ​​题目​​
• ​​递归​​
• ​​循环迭代​​
• ​​小结​​

• ​​最后​​

前言

---

2022 9/30 12:36

路漫漫其修远兮,吾将上下而求索

---

第一季：5递归与迭代

题目

编程题：
有 n 步台阶，一次只能上 1 步或者 2 步，共有多少种走法？

1.递归
2.循环迭代

递归

斐波那契数列

package fbnq5;

import org.junit.Test;

public class TestStep {
@Test
public void test() {
long start=System.currentTimeMillis();
System.out.println(f(40));//165580141
long end=System.currentTimeMillis();
System.out.println(end-start);//335
    }

//实现f(n):求n步台阶，一个有几种走法
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);
    }

}

循环迭代

package fbnq5;

import org.junit.Test;

public class TestStep {
@Test
public void test() {
long start=System.currentTimeMillis();
System.out.println(f(40));//165580141
long end=System.currentTimeMillis();
System.out.println(end-start);//335
    }

//实现f(n):求n步台阶，一个有几种走法
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);
    }

}

小结

• 方法调用自身称为递归，利用变量的原值推出新值称为迭代。
• 递归

• 优点：大问题转为小问题，可以减少代码量，同时代码精简，可读性好;
• 缺点：递归调用浪费了空间，而且递归太深容易造成堆栈的溢出。

• 迭代

• 优点：代码运行效率好，因为时间复杂度为0(n),而且没有额外空间的开销;
• 缺点:代码不如递归简洁，可读性好

最后

---

2022 9/30 13:11

---

p5

---

Markdown 1251 字数 121 行数 当
HTML 1053 字数 69 段落

---