Java教程

递归与非递归之斐波那契,阶乘,汉诺塔。

本文主要是介绍递归与非递归之斐波那契,阶乘,汉诺塔。,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

什么是递归?

   在数学与计算机科学中,递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上,递归,顾名思义,其包含了两个意思:递 和 归,这正是递归思想的精华所在。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况,这也正是递归的定义所在。格外重要的是,这个解决问题的函数必须有明确的结束条件,否则就会导致无限递归的情况。

而我们说的非递归通俗的说就是不用到递归

而常见的几种问题就是我们标题中提到的三个问题

1.斐波那契

斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……
* 在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)

其代码可如下:

#include<stdio.h>


long long fibo(long long i){
	if(i == 1){
		return 1;
	}
	if(i == 2){
		return 1;
	}
	if(i > 2){
		return fibo(i - 1) + fibo(i - 2);
	}
}
long long fibo2(long long n){
	if(n == 1){
		return 1;
	}
	if(n == 2){
		return 1;
	}
	long long f1, f2, f3;
	f1 = 1; f2 = 1;
	for(int i = 3; i <= n; i++){
		f3 = f2 + f1;
		f1 = f2;
		f2 = f3;
	}
	return f3;
}
int main(){
	
	
	long long i, sum;
    scanf("%d",&i);
    sum = fibo2(i);
    printf("非递归%lld\n",sum);
    sum = fibo(i);
    printf("递归%lld\n",sum);

	return 0;
}

2.阶乘

n!=1*2*3*....*n

其递归与非递归代码可如下

#include<stdio.h>

int jc(int n){
	if(n == 0){
		return 1;
	}
	if(n == 1){
		return 1;
	}
	if(n > 2){
		return n * jc(n - 1);
	}
}

int jc2(int n){
	int sum = 1;
	for(int i = 1; i <=n; i++){
		sum = sum * i;
	}
	return sum;
}

int main(){

    int i, sum;
    scanf("%d",&i);
    sum = jc2(i);
    printf("%d ",sum);
	return 0;
}

3.汉诺塔

古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。
* 有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,
* 小盘在上。在移动过程中可以利用B座。要求输入层数,运算后输出每步是如何移动的。

其代码可如下:

#include <stdio.h>

int sum = 0; 
void hanoi(int n , char A , char B , char C)//n个圈圈在柱子A上,借助柱子B,移动到柱子C上
{
	sum++;
  if(n == 1)//如果A柱子上只有一个圈圈,直接移动到C上
    printf("%c --> %c\n",A,C);
  else
  {
    hanoi(n-1,A,C,B);//将A柱子上的n-1个圈圈,借助柱子C,移动到柱子B上
    printf("%c --> %c\n",A,C);//将A柱子上的最后一个圈圈移动到柱子C上
    hanoi(n-1,B,A,C);//将B柱子上的n-1个圈圈,借助柱子A,移动到柱子C上
  }
}
 
int main()
{
  hanoi(8,'A','B','C');
  printf("%d",sum);
  return 0;
}

这篇关于递归与非递归之斐波那契,阶乘,汉诺塔。的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!