每天一道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.找到递归的出口,即推出的条件


目录
相关文章
|
2天前
|
C语言
C语言--函数递归与迭代
C语言--函数递归与迭代
|
9天前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
22 7
TU^
|
9天前
|
机器学习/深度学习 C语言
C语言之函数递归
C语言之函数递归
TU^
13 1
|
18天前
|
算法 测试技术 C语言
初阶编程题积累(1)------[C语言]
初阶编程题积累(1)------[C语言]
15 2
|
18天前
|
算法 C语言
初阶编程题积累(2)------[C语言]
初阶编程题积累(2)------[C语言]
11 1
|
2天前
|
C语言
C语言----递归--n的k次方
C语言----递归--n的k次方
|
2天前
|
C语言
C语言---循环迭代的方式求第n个斐波那契数
C语言---循环迭代的方式求第n个斐波那契数
|
2天前
|
C语言
C语言---函数递归
C语言---函数递归
|
2天前
|
C语言
C语言---递归---输入一个整函数,按照顺序打印每一位
C语言---递归---输入一个整函数,按照顺序打印每一位
|
2天前
|
C语言
C语言---递归--求n的阶乘
C语言---递归--求n的阶乘