首页 > 编程学习 > 第一季:5递归与迭代【Java面试题】

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

发布时间:2022/10/1 18:25:24

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

  • 前言
  • 推荐
  • 第一季:5递归与迭代
    • 题目
    • 递归
    • 循环迭代
    • 小结
  • 最后

前言


2022 9/30 12:36

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


本文是根据尚硅谷学习所做笔记

仅供学习交流使用,转载注明出处


推荐

【尚硅谷经典Java面试题第一季(java面试精讲)-哔哩哔哩】

第一季:5递归与迭代

题目

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

1.递归
2.循环迭代

递归

斐波那契数列
0227

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);
    }

}

循环迭代

1141

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 段落


Copyright © 2010-2022 kler.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号