C语言:递归(新手入门)

简介: C语言:递归(新手入门)

前言

再写这篇文章之前,其实我已经写过一篇有关递归的文章了,但考虑到那篇文章是有关二叉树的,对于刚入门的朋友来说,是有难度的。所以,才有这篇有关递归入门的文章。(有兴趣的朋友可以去看看:二叉树深度优先探索相关题目

递归简介

在C语言中,函数是允许调用自己的,这种调用过程称之为递归。而递归,顾名思义就是在传递函数的调用和归还函数的结果。递归有大事化小的能力,写起代码来很容易,而理解起来却很抽象。


由图片知道,递归是需要条件来结束递归的,否则将会无限递归下去。

一般来说,可以使用循环的地方通常都可以使用递归。

递归使用三板斧

1.确定是否能用递归

当某个特性可以被重复或者有规律性执行,一般来说都可以使用递归。

2.确定终止条件

在使用递归函数时,要想好什么时候要停下来,找好终止所需条件。

3.找出递归关系式

使用递归时,我们要想好需要传递什么,返回什么,写好关系式。当然,要清楚函数所求结果是什么。一般来说,我们可以从简单例子入手


例子

下面将通过两个例子来讲解这三板斧的使用。

1.斐波那契数

这是递归使用一个非常经典的例子,

有这样一个数列:1,1,2,3,5,8,13,21…从第三个数开始,每个数是前两个数之和。求第n个数是多少?

三板斧使用

   由题目知道,第三个数开始,每个数是前两个数之和,这种规律性符合我们
   使用递归;例如我们求第三个数,我们很容易知道是1+1=2,但我们此时
   要想好怎么把这个关系式转换成递归的关系式。第一个1为第一个数,第二个
   为第二个数,那么就将他转换为函数形式即可。这时我们很容易知道,n进入
   函数后是不断递减的,那么终止条件(传递函数的终点)就是第一个数和第二个
   数。

代码

#include<stdio.h>
 int fib(int n)
 {
 //递归终止条件
     if(n==1||n==2)
    {
         return 1;
     }
     //递归关系式
     return fib(n-1)+fib(n-2);
 }
 int main()
 {
 int n=5;
 int sum=fib(n);
 printf("%d",sum);
 return 0;
 }


  结果为:5


2.计算n的k次方

三板斧使用

通过n多次乘自己,很清楚能使用递归。例如,求2的3次方

由图知,当次方为1时,就是终止条件;而关系式就是n*后面的数。


#include<stdio.h>
int power(int n,int k)
{
    if(k==1)
    {
        return n;
    }
        return n*power(n,k-1);
}
int main()
{
  power(2,5);
  return 0;
}
   结果:32


循环和递归

上面我们说过,一般能循环的话都能进行递归。有时用循环解决问题比较好,但有时用递归更好。递归方案更简洁,但效率却没有循环高。

例如,求n的阶乘。

代码如下:

#include<stdio.h>
//递归形式
int Fab(int n)
{
    if(n==1)
    {
        return 1;
    }
    return Fab(n-1)*n;
}
//循环迭代形式
int Fab(int n)
{
    int sum=1;
   for(int i=1;i<n;i++)
    {
        sum=sum*(i+1);
    }
    return sum;
}
int main()
{
    int n=5;
    int sum=Fab(n);
    printf("%d",sum);
    return 0;
}


结果:120

如果看代码的话,我们看得出递归形式明显简洁很多,但实际上,它在使用的过程中是很复杂的。为什么这么说呢?我们知道,调用函数要在内存中临时开辟一块空间进行存储,结束了函数就会归还这块空间(栈区)。递归函数在使用过程中,总是在函数没有使用完就又进入了下一个函数,函数又得开辟空间,循环往复,内存就占用比较多。而循环只是在一个函数内进行使用,故只开辟了一块空间。


所以,如果一个函数能使用递归和循环的情况下,优先选择循环

递归函数放置的顺序问题

在使用递归过程中,要清楚先做什么再做什么。递归的函数放想要执行语句前还是后,是非常关键的。

如:想将一个整数打印成一个数一个数且数中间用空格隔开。

例子:将1729打印成 1 7 2 9

代码:

#include<stdio.h>
void printf_lone(int n)
{
    if(n<10)
    {
        printf("%d ",n);
        return;
    }
    printf("%d ",n%10);
    printf_lone(n/10);
}
int main()
{
    int n=1729;
    printf_lone(n);
    return 0;
}
结果:9 2 7 1

结果竟然和我们想要的结果相反,这时我们就要考虑一下我们的递归思想有没有错误。通过思考,发现我们是从数的右边到数的左边。当我们先打印时,那肯定是先打印9 了,依次递归,那么结果就呈现相反的了。所以,正确的代码是:

#include<stdio.h>
void printf_lone(int n)
{
    if(n<10)
    {
        printf("%d ",n);
        return;
    }
    printf_lone(n/10);
    printf("%d ",n%10);
}
int main()
{
    int n=1729;
    printf_lone(n);
    return 0;
}


结果 :1 7 2 9

所以,我们要清楚递归是从哪到哪的,先执行什么,后执行是什么,才能写出正确的代码。

总结

在这里,就简单介绍了递归的使用方法和一些注意事项,由上面例子清楚,我们的终止条件一般都会放在前头,然后才是递归关系式。如果你想巩固递归思想,可以通过专项练习进行巩固。在C语言后面学习道路上,这个递归思想还是非常重要的,不是循环所能解决的。

好了,今天就先到这里,感谢你的观看。

相关文章
|
2月前
|
安全 编译器 C语言
C++入门1——从C语言到C++的过渡
C++入门1——从C语言到C++的过渡
70 2
|
4月前
|
机器学习/深度学习 C语言
九/十:《初学C语言》— 扫雷游戏实现和函数递归基础
【8月更文挑战第5天】本篇文章用C语言采用多文件编写实现了一个基础的扫雷游戏(附源码),并讲解了关于函数递归的基础概念及其相对应的习题练习(附源码)
46 1
九/十:《初学C语言》— 扫雷游戏实现和函数递归基础
|
21天前
|
存储 NoSQL 编译器
【C语言】指针的神秘探险:从入门到精通的奇幻之旅 !
指针是一个变量,它存储另一个变量的内存地址。换句话说,指针“指向”存储在内存中的某个数据。
74 3
【C语言】指针的神秘探险:从入门到精通的奇幻之旅 !
|
2月前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
71 7
|
2月前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
44 2
|
2月前
|
存储 Java 编译器
初识C语言1——C语言入门介绍
初识C语言1——C语言入门介绍
36 1
|
2月前
|
C语言
c语言回顾-函数递归(下)
c语言回顾-函数递归(下)
42 0
|
2月前
|
C语言
回溯入门题,数据所有排列方式(c语言)
回溯入门题,数据所有排列方式(c语言)
|
4月前
|
C语言
C语言------程设设计入门
这篇文章是C语言程序设计的入门教程,涵盖了C程序的实现过程、VC集成开发环境的使用、基本数据类型的使用、格式控制字符的作用,以及通过示例代码演示了如何使用printf()函数输出不同类型的数据。
C语言------程设设计入门
|
4月前
|
机器学习/深度学习 C语言
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
要保持最小的步数,每一次汉诺塔问题(无论是最初还是递归过程中的),如果此时初始柱盘子数为偶数,我们第一步是把最上面的盘子移动到中转柱,如果为奇数,我们第一步则是将其移动到目标柱。
104 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)