每天一道C语言编程(递归:斐波那契数,母牛的故事)

简介: 每天一道C语言编程(递归:斐波那契数,母牛的故事)

递归的条件


递归函数必须有一个可直接退出的条件,否则会进入无限递归,例如


#include<stdio.h>
void f(int n)
{
  if(n<0)
  return;
  f(n-1);
  printf("%d ",n);
}
int main()
{
  int n=5;
  f(n);
  return 0;
}

//递归的出口

if(n<0)

       return;


调用的过程如图所示



注:


• 递归调用时,函数的栈内存的变化如下图所示。可见,随着递归函数的层层深入,栈空间逐渐往下增长,如果递归的层次太深,很容易把栈内存耗光。

•层层递进时,问题的规模会随之减小,减小到可直接退出的条件时,函数开始层层回归。



接下来看几个练习


题目描述

有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?


输入格式

输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0<n<55),n的含义如题目中描述。

n=0表示输入数据的结束,不做处理。


输出格式

对于每个测试实例,输出在第n年的时候母牛的数量。

每个输出占一行。


样例输入

2

4

5

0

样例输出

2

4

6

根据每四年生一头小母牛,可列出表格:

年份 1 2 3 4 5 6 7 8 9

母牛数量 1 2 3 4 6 9 13 19 28

观察规律得到



代码如下


# include<stdio.h>
int fun(int n)
{
    if(n<=3) return n;
    else return fun(n-1)+fun(n-3);
}
int main()
{
    int n;
    while(scanf("%d",&n) && n)
/*
如果n不为0,则进入循环,也可以写为
while(treue)
{
    scanf("%d",&n);
    if(n==0)
        break;
}
*/
        printf("%d\n",fun(n));
    return 0;
}


类似于斐波那契数


1、1、2、3、5、8、13、21、34 ……

斐波那契数列的规律是,除了最开头的两项之外,其余任意一项的值等于前两项之和。而开头的两项都是1。用数学公式表达是:



#include <stdio.h>
int fibonacci(int num)
{
    // 第1和第2个斐波那契数不需要经过任何计算,规定都是1
    if(num == 1 || num == 2)
        return 1;
   
    // 第N个斐波那契数,等于第N-1个和第N-2个斐波那契数之和
    return (fibonacci(num-1) + fibonacci(num-2));
}
int main(void)
{
 
    int num;
    scanf("%d", &num); 
    printf("第 %d 个斐波那契数是: %d\n", num, fibonacci(num));
    return 0;
}


编写一个函数,给出底数x和幂函数 N,计算,例如


float ans1 = myPower(4, 2);     // 4的2次方
float ans2 = myPower(3.14, -2); // 3.14的-2次方

运用递归


=


可得代码如下


#include<stdio.h>
 float f(float x,int n)
 {
  if(n==0)
    return 1;
  else
    return f(x,n-1)*x;
 }
 int main()
 {
  float x;
  int n;
  scanf("%f %d",&x,&n);
  if(x==0)
    printf("0");
  
    //除0之外的任何数的0次幂=1 
  else if(x != 0 && n == 0)
  printf("%f^%d = 1\n", x, n);
  //负整数次幂 
  else if(n<0)
  {
  n*=-1;
  printf("%f^-%d=%.6f",x,n,1/f(x,n));
  }
  //正整数次幂 
  else
    {
        printf("%f^%d = %.6f\n", x, n, f(x, n));
    }
  return 0;
 }


结果示例



总结


1.递归代码编写之前,一定要观察f(n)与f(n-1)之间的关系,判断是否适合用递归编写


2.找到递归的出口,即推出的条件


目录
相关文章
|
12天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
35 7
|
1月前
|
NoSQL C语言 索引
十二个C语言新手编程时常犯的错误及解决方式
C语言初学者常遇错误包括语法错误、未初始化变量、数组越界、指针错误、函数声明与定义不匹配、忘记包含头文件、格式化字符串错误、忘记返回值、内存泄漏、逻辑错误、字符串未正确终止及递归无退出条件。解决方法涉及仔细检查代码、初始化变量、确保索引有效、正确使用指针与格式化字符串、包含必要头文件、使用调试工具跟踪逻辑、避免内存泄漏及确保递归有基准情况。利用调试器、编写注释及查阅资料也有助于提高编程效率。避免这些错误可使代码更稳定、高效。
131 12
|
23天前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
30 2
|
2月前
|
存储 算法 Linux
C语言 多进程编程(一)进程创建
本文详细介绍了Linux系统中的进程管理。首先,文章解释了进程的概念及其特点,强调了进程作为操作系统中独立可调度实体的重要性。文章还深入讲解了Linux下的进程管理,包括如何获取进程ID、进程地址空间、虚拟地址与物理地址的区别,以及进程状态管理和优先级设置等内容。此外,还介绍了常用进程管理命令如`ps`、`top`、`pstree`和`kill`的使用方法。最后,文章讨论了进程的创建、退出和等待机制,并展示了如何通过`fork()`、`exec`家族函数以及`wait()`和`waitpid()`函数来管理和控制进程。此外,还介绍了守护进程的创建方法。
C语言 多进程编程(一)进程创建
|
23天前
|
C语言
c语言回顾-函数递归(下)
c语言回顾-函数递归(下)
35 0
|
2月前
|
Linux C语言
C语言 多进程编程(三)信号处理方式和自定义处理函数
本文详细介绍了Linux系统中进程间通信的关键机制——信号。首先解释了信号作为一种异步通知机制的特点及其主要来源,接着列举了常见的信号类型及其定义。文章进一步探讨了信号的处理流程和Linux中处理信号的方式,包括忽略信号、捕捉信号以及执行默认操作。此外,通过具体示例演示了如何创建子进程并通过信号进行控制。最后,讲解了如何通过`signal`函数自定义信号处理函数,并提供了完整的示例代码,展示了父子进程之间通过信号进行通信的过程。
|
2月前
|
Linux C语言
C语言 多进程编程(四)定时器信号和子进程退出信号
本文详细介绍了Linux系统中的定时器信号及其相关函数。首先,文章解释了`SIGALRM`信号的作用及应用场景,包括计时器、超时重试和定时任务等。接着介绍了`alarm()`函数,展示了如何设置定时器以及其局限性。随后探讨了`setitimer()`函数,比较了它与`alarm()`的不同之处,包括定时器类型、精度和支持的定时器数量等方面。最后,文章讲解了子进程退出时如何利用`SIGCHLD`信号,提供了示例代码展示如何处理子进程退出信号,避免僵尸进程问题。
|
2月前
|
消息中间件 Unix Linux
C语言 多进程编程(五)消息队列
本文介绍了Linux系统中多进程通信之消息队列的使用方法。首先通过`ftok()`函数生成消息队列的唯一ID,然后使用`msgget()`创建消息队列,并通过`msgctl()`进行操作,如删除队列。接着,通过`msgsnd()`函数发送消息到消息队列,使用`msgrcv()`函数从队列中接收消息。文章提供了详细的函数原型、参数说明及示例代码,帮助读者理解和应用消息队列进行进程间通信。
|
2月前
|
缓存 Linux C语言
C语言 多进程编程(六)共享内存
本文介绍了Linux系统下的多进程通信机制——共享内存的使用方法。首先详细讲解了如何通过`shmget()`函数创建共享内存,并提供了示例代码。接着介绍了如何利用`shmctl()`函数删除共享内存。随后,文章解释了共享内存映射的概念及其实现方法,包括使用`shmat()`函数进行映射以及使用`shmdt()`函数解除映射,并给出了相应的示例代码。最后,展示了如何在共享内存中读写数据的具体操作流程。
|
2月前
|
消息中间件 Unix Linux
C语言 多进程编程(二)管道
本文详细介绍了Linux下的进程间通信(IPC),重点讨论了管道通信机制。首先,文章概述了进程间通信的基本概念及重要性,并列举了几种常见的IPC方式。接着深入探讨了管道通信,包括无名管道(匿名管道)和有名管道(命名管道)。无名管道主要用于父子进程间的单向通信,有名管道则可用于任意进程间的通信。文中提供了丰富的示例代码,展示了如何使用`pipe()`和`mkfifo()`函数创建管道,并通过实例演示了如何利用管道进行进程间的消息传递。此外,还分析了管道的特点、优缺点以及如何通过`errno`判断管道是否存在,帮助读者更好地理解和应用管道通信技术。