递归与尾递归总结

1、递归

关于递归的概念,我们都不陌生。简单的来说递归就是一个函数直接或间接地调用自身,是为直接或间接递归。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。用递归需要注意以下两点:(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

递归一般用于解决三类问题:

(1)数据的定义是按递归定义的。(Fibonacci函数,n的阶乘)

  (2)问题解法按递归实现。(回溯)

  (3)数据的结构形式是按递归定义的。(二叉树的遍历,图的搜索)

递归的缺点:

递归解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。

int FibonacciRecursive(int n)
{
     if( n < 2)
        return n;
     return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
 }

用线性递归实现Fibonacci函数,程序如下所示:

int FibonacciRecursive(int n)
{
     if( n < 2)
        return n;
     return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
 }

递归写的代码非常容易懂,完全是根据函数的条件进行选择计算机步骤。例如现在要计算n=5时的值,递归调用过程如下图所示:

2、尾递归

  顾名思义,尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。

  尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈,而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可,之前的可优化删去。

  采用尾递归实现Fibonacci函数,程序如下所示:

int FibonacciTailRecursive(int n,int ret1,int ret2)
{
    if(n==0)
       return ret1; 
     return FibonacciTailRecursive(n-1,ret2,ret1+ret2);
}

例如现在要计算n=5时的值,尾递归调用过程如下图所示:

从图可以看出,为递归不需要向上返回了,但是需要引入而外的两个空间来保持当前的结果。

  为了更好的理解尾递归的应用,写个程序进行练习。采用直接递归和尾递归的方法求解单链表的长度,C语言实现程序如下所示:

  #include <stdio.h>
  #include <stdlib.h>
  
  typedef struct node
  {
    int data;
    struct node* next;
  }node,*linklist;
 
 void InitLinklist(linklist* head)
 {
      if(*head != NULL)
         free(*head);
      *head = (node*)malloc(sizeof(node));
      (*head)->next = NULL;
 }
 
 void InsertNode(linklist* head,int d)
 {
      node* newNode = (node*)malloc(sizeof(node));
      newNode->data = d;
      newNode->next = (*head)->next;      
      (*head)->next = newNode;

 }
 
 //直接递归求链表的长度 
 int GetLengthRecursive(linklist head)
 {
     if(head->next == NULL)
        return 0;
     return (GetLengthRecursive(head->next) + 1);
 }
 //采用尾递归求链表的长度,借助变量acc保存当前链表的长度,不断的累加 
 int GetLengthTailRecursive(linklist head,int *acc)
 {
     if(head->next == NULL)
       return *acc;
     *acc = *acc+1;
     return GetLengthTailRecursive(head->next,acc);
 }
 
 void PrintLinklist(linklist head)
 {
      node* pnode = head->next;
      while(pnode)
      {
         printf("%d->",pnode->data);
         pnode = pnode->next;
      }
      printf("->NULL\n");
 }
 
 int main()
 {
     linklist head = NULL;
     int len = 0;
     InitLinklist(&head);
     InsertNode(&head,10);
     InsertNode(&head,21);
     InsertNode(&head,14);
     InsertNode(&head,19);
     InsertNode(&head,132);
     InsertNode(&head,192);
     PrintLinklist(head);
     printf("The length of linklist is: %d\n",GetLengthRecursive(head));
     GetLengthTailRecursive(head,&len);
     printf("The length of linklist is: %d\n",len);
     system("pause");
 }

程序测试结果如下图所示:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏路人甲Java

玩转Mysql系列 - 第24篇:如何正确的使用索引?

学习索引,主要是写出更快的sql,当我们写sql的时候,需要明确的知道sql为什么会走索引?为什么有些sql不走索引?sql会走那些索引,为什么会这么走?我们需...

13020
来自专栏林德熙的博客

dotnet 列表 Linq 的 Task 用法

在 dotnet 可以使用 Take 获取指定数量的元素,获取顺序是从前向后,而获取到的数量是小于等于传入的指定数量。如数组中元素的数量小于传入的指定数量,则返...

9210
来自专栏数据魔术师

AlphaZero登上《科学》封面:一个算法“通杀”三大棋,完整论文首次发布

不仅会下围棋,还自学成才横扫国际象棋和日本将棋的DeepMind AlphaZero,登上了最新一期《科学》杂志封面。

10860
来自专栏数据魔术师

遗传算法求解混合流水车间调度问题(附C++代码)

各位读者大家好,好久没有介绍算法的推文了,感觉愧对了读者们热爱学习的心灵。于是,今天我们带来了一个神奇的优化算法——遗传算法!

13080
来自专栏数据魔术师

十大经典排序算法(动图演示,收藏好文)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

13050
来自专栏时间之外沉浮事

【推荐】来自法国的混合仿真平台hynesim

法国著名的网络靶场hns-platform项目基于开源的由MinDef/DGA/Celar(FR)资助的Hynesim项目(http://www.hynesim...

11610
来自专栏Java识堂

消灭 Java 代码的“坏味道”

代码中的"坏味道",如"私欲"如"灰尘",每天都在增加,一日不去清除,便会越累越多。如果用功去清除这些"坏味道",不仅能提高自己的编码水平,也能使代码变得"精白...

8610
来自专栏数据魔术师

Python AI 教学 | KNN算法及应用

简单来说,KNN可以看成有一堆你已经知道其所属类别的数据(训练数据),然后当一个新数据进入的时候,就开始跟训练数据里的每个点求距离,然后挑离这个新数据最近的K个...

11150
来自专栏数据魔术师

分治法(Divide-and-Conquer Algorithm)经典例子分析

上一篇文章里给大家介绍了归并排序,今天首先给大家带来同样运用分治法来解决问题的快速排序。

7430
来自专栏知识分享

关于单片机的RAM

7420

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励