递归与尾递归总结

简介:

1、递归

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

递归一般用于解决三类问题:
   (1)数据的定义是按递归定义的。(Fibonacci函数,n的阶乘)
   (2)问题解法按递归实现。(回溯)
   (3)数据的结构形式是按递归定义的。(二叉树的遍历,图的搜索)
递归的缺点:
  递归解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出
  用线性递归实现Fibonacci函数,程序如下所示:
1 int FibonacciRecursive(int n)
2 {
3     if( n < 2)
4         return n;
5     return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
6 }

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

2、尾递归

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

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

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

1 int FibonacciTailRecursive(int n,int ret1,int ret2)
2 {
3    if(n==0)
4       return ret1; 
5     return FibonacciTailRecursive(n-1,ret2,ret1+ret2);
6 }

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

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

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

复制代码
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct node
 5 {
 6   int data;
 7   struct node* next;
 8 }node,*linklist;
 9 
10 void InitLinklist(linklist* head)
11 {
12      if(*head != NULL)
13         free(*head);
14      *head = (node*)malloc(sizeof(node));
15      (*head)->next = NULL;
16 }
17 
18 void InsertNode(linklist* head,int d)
19 {
20      node* newNode = (node*)malloc(sizeof(node));
21      newNode->data = d;
22      newNode->next = (*head)->next;
23      (*head)->next = newNode;
24 }
25 
26 //直接递归求链表的长度 
27 int GetLengthRecursive(linklist head)
28 {
29     if(head->next == NULL)
30        return 0;
31     return (GetLengthRecursive(head->next) + 1);
32 }
33 //采用尾递归求链表的长度,借助变量acc保存当前链表的长度,不断的累加 
34 int GetLengthTailRecursive(linklist head,int *acc)
35 {
36     if(head->next == NULL)
37       return *acc;
38     *acc = *acc+1;
39     return GetLengthTailRecursive(head->next,acc);
40 }
41 
42 void PrintLinklist(linklist head)
43 {
44      node* pnode = head->next;
45      while(pnode)
46      {
47         printf("%d->",pnode->data);
48         pnode = pnode->next;
49      }
50      printf("->NULL\n");
51 }
52 
53 int main()
54 {
55     linklist head = NULL;
56     int len = 0;
57     InitLinklist(&head);
58     InsertNode(&head,10);
59     InsertNode(&head,21);
60     InsertNode(&head,14);
61     InsertNode(&head,19);
62     InsertNode(&head,132);
63     InsertNode(&head,192);
64     PrintLinklist(head);
65     printf("The length of linklist is: %d\n",GetLengthRecursive(head));
66     GetLengthTailRecursive(head,&len);
67     printf("The length of linklist is: %d\n",len);
68     system("pause");
69 }
复制代码

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

相关文章
|
2月前
什么是递归函数?怎样实现递归?
什么是递归函数?怎样实现递归?
|
1月前
递归函数
【6月更文挑战第9天】递归函数。
21 4
|
2月前
|
算法
递归函数实现素数判断
该文介绍了素数判断的递归实现,尽管递归算法在判断素数上并不高效,时间复杂度和空间复杂度均为O(N),但作为学习和理解递归的一种方式,仍有其价值。文章强调在实际应用中应选择更高效的方法。递归思路基于试除法,对于大于1的整数,如果只能被1和自身整除,则为素数。递归函数通过不断试除2到根号下该数之间的数来判断,同时注意到偶数不是素数。文中给出了非递归和递归的试除法代码示例。
48 2
|
1月前
|
C语言
C语言函数递归详解:理解递归的原理与应用
C语言函数递归详解:理解递归的原理与应用
23 0
2705:扩号匹配问题(递归与非递归)
题目链接:http://noi.openjudge.cn/ch0202/2705/ 总时间限制:1000ms内存限制:65536kB 描述 在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。
2085 0
|
9月前
尾递归
尾递归是一种递归函数优化技术,它指的是在递归函数的最后一步操作中,调用自身并返回结果,而不进行任何其他操作。尾递归可以有效地减少递归调用的次数,从而提高程序的执行效率。
32 5
|
机器学习/深度学习
递归函数问题
递归函数问题
49 0
|
算法 Python
递归的使用
递归的使用
37 0
|
Java C语言
递归就这么简单(上)
本来预算此章节是继续写快速排序的,然而编写快速排序往往是递归来写的,并且递归可能不是那么好理解,于是就有了这篇文章。
158 0
递归就这么简单(上)