注意：java不支持尾递归，在使用递归是主要考虑输出结果的相似性。

如果相似性很不明显，需要主动构造相似性，不能相似的原因可能是缺少参数，递归与数学上的递推公式很类似。

题目：2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：2^0 = 1
示例 2：

输入：n = 16
输出：true
解释：2^4 = 16
示例 3：

输入：n = 3
输出：false
示例 4：

输入：n = 4
输出：true
示例 5：

输入：n = 5
输出：false

提示：

-2^31 <= n <= 2^31 - 1

代码

import java.util.Scanner;

class Solution {
    public static boolean isPowerOfTwo(int n) {
        if(n==1) return true;
        if(n==0) return false;
        if(n%2!=0) return false;
        return isPowerOfTwo(n/2);

    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(isPowerOfTwo(n));
    }
}

题目：合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

代码

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1==null) return list2;
        if (list2==null) return list1;
        ListNode res = list1.val< list2.val?list1:list2;
        res.next= mergeTwoLists(res.next,list1.val>=list2.val?list1:list2);
        return res;

    }
    }

题目:3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例 1：

输入：n = 27
输出：true
示例 2：

输入：n = 0
输出：false
示例 3：

输入：n = 9
输出：true
示例 4：

输入：n = 45
输出：false

提示：

-2^31 <= n <= 2^31 - 1

代码

import java.util.Scanner;

class Solution {
    public static boolean isPowerOfThree(int n) {
        if (n>=1){
            if (n==3||n==1){
                return true;
            }else if (n%3==0){
                return isPowerOfThree(n/3);
            }else{
                return false;
            }
        }
        else{
            return false;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(isPowerOfThree(n));
    }
}