java递归算法面试题常见有哪些?

TheDisguiser 2020-09-07 17:20:13 java常见问答 9129

对于java基础算法之一的递归,在java程序员面试时,是极大概率会被问到的,所以提前准备是必须的,下面我们来了解一些常见的递归算法面试题。

一、用递归实现买汽水一个人买汽水,一块钱一瓶汽水,三个瓶盖可以换一瓶汽水,两个空瓶可以换一瓶汽水

问20块钱可以买多少汽水?

首先分析:

一瓶汽水:1soda = 1cap +1bottle;

两个空瓶:2bottle = 1soda;

三个瓶盖:3cap = 1soda;

那么递归退出条件就是: cup<3&&bottle<2 &&soda<1

因为在这个过程中,三个元素soda, cup, bottle都有连续的变化,所以递归调用时要将三个参数都传进去。

代码:

private int Total(int soda, int cap, int bottle)
{}
public class DiGui02
{
    public static void main(String[] args)
    {
        int total = Total(20, 0, 0);
        System.out.println(total);
    }
    public static int Total(int Total, int caps, int bottles)
    {
        caps %= 3;
        bottles %= 2;
        caps += Total;
        bottles += Total;
        if (caps < 3 && bottles < 2)
        {
            return Total;
        }
        else
        {
            return Total(caps / 3 + bottles / 2, caps, bottles) + Total;
        }
    }
}

二、定义一个整数,大于0,不用循环和本地变量,按照n,2n,4n,8n的顺序递增,当值大于5000时,把值按照指定顺序输出来。

代码:

package com.swift;
public class Digui_Dizeng_Dijian
{
    public static void main(String[] args)
    {
        /*
         * 一个整数,大于0,不用循环和本地变量,按照n,2n,4n,8n的顺序递增,当值大于5000时,把值按照指定顺序输出来。 例:n=1237 则输出为:
         * 1237, 2474, 4948, 9896, 9896, 4948, 2474, 1237,
         */
        int n = 1237;
        dizeng(n);
        System.out.println(sum(100));
    }
    //无返回值递归
    public static void dizeng(int n)
    {
        System.out.println(n);
        if (n > 9000)
        {
            dijian(n);
        }
        if (n < 5000)
        {
            dizeng(n * 2);
        }
    }
    public static void dijian(int n)
    {
        System.out.println(n);
        if (n == 1237)
        {
            System.exit(0);
        }
        else
        {
            dijian(n / 2);
        }
    }
    //有返回值递归
    public static int sum(int num)
    {
        if (num > 1)
        {
            return num + sum(num - 1);
        }
        else
        {
            return 1;
        }
    }
}

三、实现斐波那契数列

代码:

public class Recursion
{
    public static long factorial(int i)
    {
        if (i < 0)
            return -1;
        else if (i == 0 || i == 1)
            return 1;
        else
            return i * factorial(i - 1);
    }
    public static int sum(int i)
    {
        if (i == 0)
            return 0;
        else
            return i + sum(i - 1);
    }
    public static int fibonacci(int i)
    {
        if (i == 0 || i == 1)
            return 1;
        else
            return fibonacci(i - 1) + fibonacci(i - 2);
    }
    public static void main(String[] args)
    {
        for (int i = 0; i < 5; i++)
        {
            System.out.println(i + "!= " + factorial(i));
            System.out.println("sum(" + i + "!) = " + sum(i));
            System.out.println("fibonacci(" + i + ")= " + fibonacci(i));
            System.out.println("=========================");
        }
    }
}

以上就是今天的全部内容,关于java面试题的所有内容就到这了,更多详细知识请关注本网站了解具体。

推荐阅读:

java成员变量和方法的含义是什么?异同点有哪些?

java简单编程题问第五个人多少岁?java递归算法经典实例

求二叉树深度的递归算法java