递归算法练习

简介: 递归算法练习

 递归算法是所有算法中较难的一种,依靠他代码的简洁和清晰地逻辑很受人们喜欢,但是新手入门递归还是会被他不同寻常的思路吓到,其实面对递归问题我们只需要看清题目,分析出要求,有清晰的解题思路,只要仔细分析,就会很简单的解决问题。

 提到递归,大多数题目就都离不开二叉树,这只不过是其中的一种,我们来做一做其他类型的题目,提高我们分析递归问题的逻辑能力和分析能力,由浅入深,从而掌握递归。

第一题

合并两个有序链表

这道题我们可以搞一个虚拟节点,很容易就能解决这道问题。

 但是如果我们用递归的方法去解决这道题目,我们需要思考递归的每一步需要做什么,将一个大问题划分为数个小问题来解决。

递归需要我们做什么呢?给定两个链表,将他们合并,然后返回头节点。

 我们判断两个链表的首元素后,假设是list1val大于list2val,就向后连接list2的节点,此时剩下的工作就是连接list1的节点和list2的剩余节点,就是list1list2剩余节点的合并问题,切记我们呢还需要返回头节点。

 递归问题还需要判断的就是何时结束,这道题目就是判断一方如果是空节点,就直接将另一方的节点连接起来就好。

 因为我们返回的是头节点,所以每次只需要将他们连接起来即可。这个操作就是使前边的节点的next等于后续返回的头节点,这样就将两个链表的节点全部连接起来了。

代码如下

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr)//遇到空节点就返回另一个节点的头指针
        {
            return list2;
        }
        if(list2==nullptr)
        {
            return list1;
        }
        if(list1->val>list2->val)
        {
            list2->next=mergeTwoLists(list1,list2->next);//接收返回的节点并链接
            return list2;
        }
        else
        {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
    }
};

第二题

反转链表

 这道题如果直接来做的话,使用一个虚拟头节点,然后定义一个节点指针一直头插就可以解决,或者就是设置三个指针变量,从前往后依次改变指针的方向。

头插法

ListNode* reverseList(ListNode* head) {
        ListNode* newnode=new ListNode;
        ListNode*cur=nullptr;
        while(head!=nullptr)
        {
            newnode->next=head;
            ListNode* next=head->next;//保留下一个节点,防止下一步操作导致链表断开
            head->next=cur;
            cur=head;
            head=next;
        }
        return newnode->next;
    }

直接改变结点指针的方法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

 如果使用递归的思想来解决这道问题,我们呢还是需要考虑递归的每一步是要做什么。

 我们需要将这个问题拆分为几个小问题来解决,不仅需要改变所有节点的指向,还要将链表的头节点返回回来。

 拆分成子问题,一直遍历到最后一个节点,将该节点返回,递归过程中不仅要将新的头节点层层返回回去,还要改变指针指向。

代码如下

ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
        {
            return head;
        }
        ListNode* newnode=reverseList(head->next);//接收返回值
        head->next->next=head;//改变指针指向
        head->next=nullptr;//统一处理
        return newnode;//层层递归返回新的头节点
    }

第三题

两两交换链表中的节点

 这道题要求我们不是修改链表的节点中存放的值,使用递归算法解决,还是要拆分问题。将一个大的问题拆分为小的子问题。

 单看每一步,我们需要做的是将两个节点翻转,返回新的头结点,至于递归结束的条件,很明显,如果只有一个节点或者节点为空就直接返回该节点即可。因为如果是空,就直接链接上了,如果只有一个节点,这个节点的next为空,依然成立。

 现在就是如何翻转两个节点并且返回新节点的问题了。如图

 接下来就是改变headcurnext的指向,因为我们已经保留k节点的指针了,所以curnext可以放心修改,然后就是接受返回值。

 在接下来的子问题中,做同样的步骤,翻转3,4节点,返回新的头结点,此时上一次递归的next指针就可以接收这个返回值,将链表连接起来。

代码如下

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* newnode=nullptr;
        if(!(head&&head->next))
        {
            return head;
        }
        ListNode*cur=head->next;
        ListNode*k=cur->next;
        head->next=swapPairs(k);
        cur->next=head;
        return cur;
    }
};

第四题

 这道题让我们求xn次幂,题目介绍很简单,这道题我们也可以直接使用库里面的函数直接解决,但是这样就体现不出这道题的意义了,来尝试一下用递归的方法解决这个问题。

首先来说直接算的话为什么不好呢?

 就比如2的8次方,我们再已经知道2的4次方是多少之后,我们可以只使用一次乘法就得出结果,但是如果一步一步算,我们还要再乘4次才能得到相应的结果。

 所以我们在求x的n次方时,可以先求出x的n/2次方,然后让他们想乘就可以了。我们写一个pow函数帮助我们实现这个功能。

此时会出现两个问题

 如果是奇数怎么办?递归出口应该是怎么样的呢?举例来分析一下

  • 29 需要计算的话,因为是奇数,所以再最后返回两个24时,还要再乘以一个2。
  • 求24时,结果是两个2^2相乘。
  • 求22时,此时为两个2相乘。如果递归的过程中,n等于1时,就直接返回x即可。

 还要注意,n有可能是负数,所以如果n为负数,就直接用1除以返回的结果,在传递参数时将n变为-n即可。

 还要注意n为0的情况,我们返回1就可以了。

 这道题还会出现数据溢出的情况,我们可以将n的类型写为long long就可以解决。

代码如下

double pow(double x, long long n)
{
    if (n == 1)
    {
        return x;
    }
    double tmp = pow(x, n / 2);
    return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
double myPow(double x, int n) {
    if(n==0)
    {
        return 1.0;
    }
    return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
}

本文到此结束,有收获还请一键三连支持哦。

目录
相关文章
|
18天前
|
存储 算法
递归算法
【10月更文挑战第11天】递归算法是一种强大而又具有挑战性的算法技术。通过深入理解和掌握递归的原理、应用以及优化方法,我们可以更好地利用它来解决各种问题,并在编程实践中发挥其独特的优势。同时,我们也要注意递归算法可能带来的性能和栈空间问题,通过合理的设计和优化来提高算法的效率和稳定性。
17 1
|
6月前
|
算法
递归算法实现二分查找
本文简要介绍了递归实现的二分查找算法,这是一种在有序列表中快速查找的策略。递归方法虽在实际应用中较少,但有助于理解递归思想,为学习数据结构中的树内容打下基础。文中提供了原版和递归版本的二分查找代码,并强调了递归算法中处理未找到情况的注意事项。此外,还提到了递归在解决复杂问题时的优势,并通过链接分享了一个关于递归实现素数判断的例子。
83 2
|
机器学习/深度学习 人工智能 算法
深入理解递归算法
概述 定义 计算机科学中,递归是一种解决计算问题的方法,其中解决方案取决于同一类问题的更小子集 In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. 比如单链表递归遍历的例子: void f(Node node) { if(node == null) { return; } print
63 0
|
6月前
|
存储 搜索推荐
【非递归版】快速排序算法(4)
【非递归版】快速排序算法(4)
42 0
递归和非递归分别实现求第n个斐波那契数
递归和非递归分别实现求第n个斐波那契数
59 0
非递归实现二叉树遍历
非递归实现二叉树遍历
51 0
|
存储 算法 JavaScript
算法系列-二叉树遍历(非递归实现)
在内卷潮流的席卷下,身为算法小白的我不得不问自己,是否得踏上征程,征服这座巍巍高山。 从零开始,终点不知何方,取决于自己可以坚持多久。 希望你可以和我一样,克服恐惧,哪怕毫无基础,哪怕天生愚钝,依然选择直面困难。
|
机器学习/深度学习 算法 前端开发
递归算法使用
通常递归算法可以将一个问题的重复调用进行分解,将其分解成一个多次调用,最终完成筛选或者需要的数据。比如我们常见的斐波那契数列就是这样的: 0、1、1、2、3、5、8、13、21、34这样的递归数据,可以通过此来总结出它的数学公式规律:F(n) = F(n-1) + F(n-2)的这个过程就是是借助上面的F(0)和F(1)的结果来进行递推的,这个过程在数学上是一个数列的递推公式,在高中我们学过的数列上。我还记得当时求解递推公式可以使用函数方程,而函数方程的思想想想其实是借助了微分方程逆推得到积分方程的过程,或者说是采用不动点法可以实现这一求解的过程。这个过程,在我看到高等数学的时候才明白,现在想
187 0
递归算法使用
汉诺塔(递归+ 非递归版)
汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上, 有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。 游戏中的每一步规则如下:
235 1
汉诺塔(递归+ 非递归版)