算法入门之递归

本文主要是介绍算法入门之递归，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

力扣习题跟"着爱学习的饲养员"练习的，感觉讲的不错

1、什么是递归算法？

递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。

2、递归应注意的问题？

• 接受的参数
• 返回值
• 终止条件
• 递归拆解

3、力扣练习题

练习题：509 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

思路：直接用递归法

public class Tem1Fib {

    public static void main(String[] args) {
        Tem1Fib fib=new Tem1Fib();
        System.out.println(fib.fib(2));
    }

    public int fib(int n) { //参数
        //递归的终止条件
        if (n==0||n==1){
            return n==1?1:0;
        }
        //递归的分解
        int sum=fib(n-1)+fib(n-2);
        //返回值
        return sum;
    }
}

练习题：206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路：用递归法，当递归下限到链表尾部时即head指向最后一个元素时，进行递归上限，让head.next.next指向链表的倒数第二个元素，让他成为head，再让head.next指向null，再次递归即可

代码实现：

public class Tem2 {
    public ListNode reverseList(ListNode head) {
        //递归终止条件
        if (head==null||head.next==null){
            return null;
        }

        //递归分解
        ListNode list = reverseList(head.next);
        //条件分析
        head.next.next=head;
        head.next=null;
        //返回值
        return list;
    }

练习题：344 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

思路：双指针加递归：定义两个指针，指向字符串的头和尾，利用递归法，将指针的头和尾交换顺序之后，分别将指针向左向右移动，当左指针大于等于右指针时，遍历结束。

代码实现：

public class Tem3 {

    public static void main(String[] args) {
        char[] s={'h','e','l','l','o'};
        Tem3 tem3=new Tem3();
        tem3.reverseString(s);
        System.out.println(String.valueOf(s));
    }

    //反转字符串
    public void reverseString(char[] s) {
        if (s==null||s.length==0){
            return ;
        }
        //定义两个指针,分别指向数组的头和尾
        int left=0;
        int right=s.length-1;

        //调用递归函数
        reverse(s,left,right);
    }

    public void reverse(char[] s,int left,int right){//参数
        //终止条件
        if (left>=right){
            return;
        }

        //分解
        reverse(s, left+1, right-1);
        //交换元素
        char tmp=s[left];
        s[left]=s[right];
        s[right]=tmp;
    }
}

这篇关于算法入门之递归的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！