遞歸法編程
『壹』 Java完整遞歸法編程
1、
public static void main(String[] args) {
System.out.println(step(10));
}
public static int step(int n){
if (n<=1)return 1;
if (n==2)return 2;
return step(n-1)+step(n-2);
}
『貳』 C語言編程:用遞歸法將一個整數n轉換成字元串。
1、新建一個工程和.c文件 ,輸入頭文件和主函數。
『叄』 C語言編程:用遞歸法做,輸出26個字母表的正序與反序。
#include
<stdio.h>
void
fa(int
i);
void
fb(int
i);
int
main(int
argc,
char
**
argv)
{
fa('a');
printf("\n");
fb('z');
printf("\n");
return
0;
}
void
fa(int
i)
{
if(i
<=
'z')
{
printf("%c
",
i);
fa(i+1);
}
}
void
fb(int
i)
{
if(i
>=
'a')
{
printf("%c
",
i);
fb(i-1);
}
}
題目的大致程序是這樣的。用遞歸來寫程序,首先要注意,什麼是遞歸,如何寫遞歸。
遞歸就是函數自己直接或間接的調用自身,寫遞歸一定要注意程序的出口。恩,剛學遞歸是會感覺遞歸有點難的,如果沒明白在聯系我吧
『肆』 什麼是遞推法和遞歸法兩者在思想上有何聯系
1、遞推法:遞推演算法是一種根據遞推關系進行問題求解的方法。通過已知條件,利用特定的遞推關系可以得出中間推論,直至得到問題的最終結果。遞推演算法分為順推法和逆推法兩種。
2、遞歸法:在計算機編程中,一個函數在定義或說明中直接或間接調用自身的編程技巧稱為遞歸。通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算,大大地減少了程序的代碼量。遞歸做為一種演算法在程序設計語言中廣泛應用。
3、兩者的聯系:在問題求解思想上,遞推是從已知條件出發,一步步的遞推出未知項,直到問題的解。從思想上講,遞歸也是遞推的一種,只不過它是對待解問題的遞推,直到把一個復雜的問題遞推為簡單的易解問題。然後再一步步的返回去,從而得到原問題的解。
(4)遞歸法編程擴展閱讀
相對於遞歸演算法,遞推演算法免除了數據進出棧的過程,也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值。
比如階乘函數:f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下: f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下: f(0)-->f(1)-->f(2)-->f(3) 由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推。
但是遞歸作為比較基礎的演算法,它的作用不能忽視。所以,在把握這兩種演算法的時候應該特別注意。
『伍』 用遞歸法編程,C語言編程
#include<stdlib.h>
#include<stdio.h>
int count=1; //保存整數的位數
void fun(char *str,int num) //遞歸函數
{ int lef=num;
if(count > 0)
{ count--;
lef%=10;
*(str+count) = (num%10)+48; //字元串從後至前進行保存,數字轉字元 +48
num/=10;
fun(str,num); //遞歸調用,直到最後一位
}
}
int main()
{ int num,numtemp;
char *str;
printf("請輸入一個整數:");
scanf("%d",&num);
numtemp = num;
while(numtemp/=10) count++;
str = (char *)malloc(count*sizeof(char)+1); //注意+1
*(str+count) = '\0';
fun(str,num);
printf("\nstr:%s\n",str);
free(str);
return 1;
}
輸入: 36825
輸出:str:36825
『陸』 C語言編程:用函數遞歸法求Fibonacci數列的前n項·
#include <stdio.h>
long int F(int n)
{
if (n==1||!n) {
return n;
}
else return F(n-1)+F(n-2);
}
int main(void)
{
int i,n;
printf("n=");
scanf("%d",&n);
for (i=0; i<n; i++) {
printf("%-10ld",F(i));
}
return 0;
}
在數理邏輯和計算機科學中
遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數,它是在某種直覺意義上是"可計算的" 。事實上,在可計算性理論中證明了遞歸函數精確的是圖靈機的可計算函數。遞歸函數有關於原始遞歸函數,並且它們的歸納定義(見下)建造在原始遞歸函數之上。但是,不是所有遞歸函數都是原始遞歸函數 — 最著名的這種函數是阿克曼函數。
以上內容參考:網路-遞歸函數
『柒』 用遞歸編程方法求n的階乘n!
思路:遞歸求階乘函數,如果輸入的參數等於1則返回1,否則返回n乘以該函數下次遞歸。
參考代碼:
#include
int fun(int n)
{
if(n==1||n==0) return 1;//如果參數是0或者1返回1
return n*fun(n-1);//否則返回n和下次遞歸的積
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",fun(n));
return 0;
}
/*
5
120
*/
【遞歸演算法的原理】
遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫
遞歸能使程序變得簡潔和清晰。
『捌』 python遞歸演算法經典實例有哪些
程序調用自身的編程技巧稱為遞歸( recursion)。遞歸做為一種演算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法。
它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算,大大地減少了程序的代碼量。
遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說,遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。
Python
是完全面向對象的語言。函數、模塊、數字、字元串都是對象。並且完全支持繼承、重載、派生、多繼承,有益於增強源代碼的復用性。Python支持重載運算符和動態類型。相對於Lisp這種傳統的函數式編程語言,Python對函數式設計只提供了有限的支持。有兩個標准庫(functools, itertools)提供了Haskell和Standard ML中久經考驗的函數式程序設計工具。
『玖』 C語言怎樣用遞歸方法編寫程序 求s=1!+2!+3!+...10!
提供思路,如果使用遞歸,主要針對階乘,因此,在主函數里提供十個數相加,用循環,然後重新定一個函數,在函數里提供遞歸的演算法,即不斷調用直至結束得到結果,然後相加就行。
如果不是使用遞歸,可使用上一次的結果乘以新增的數字,然後依次相加即可。
『拾』 C語言遞歸演算法
本人學c++,c的語法已經淡忘了,但是遞歸不管什麼語言都是一個原理
其實簡單一點來說就像數學裡面的數列的通項公式:
例如一個數列是2,4,6,8,10......
很容易就可以得到通項公式是a[n]=2*n n是大於0的整數
你肯定學過這個數列的另外一種表示方式就是: a[1]=2, a[n]=a[n-1]+2 n是大於1的整數
其實這就是一個遞歸的形式,只要你知道初始項的值,未知項和前幾項之間的關系就可以知道整個數列。
程序例子:比如你要得到第x項的值
普通循環:
for(int i=1; i<=n; i++)
if (i == x)
cout << 2*i; /*cout 相當於 c裡面的printf,就是輸出.*/
遞歸:
int a(int x) {
if (x = 1)
return 2; /* 第一項那肯定是2了,這個也是遞歸的終止條件! */
else return a(x-1)+2; /* 函數自身調用自身是遞歸的一個特色 */
比如x=4,那麼用數學表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2
其實遞歸方法最接近自然,也是最好思考的一個方法,難點就是把對象建模成遞歸形式,但是好多問題本身就是以遞歸形式出現的。
普通遞歸就是數據結構上的堆棧,先進後出。
例如上面x=4,把a(4)放入棧底,然後放入a(3),然後a(2),a(1),a(1)的值已知,出棧,a(1)=2,a(2)出棧a(2)=a(1)+2=2+2=4,a(3)出棧a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出棧a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8
再比如樓上的階乘例子,當n=0 或 1時,0!=1,1!=1,這個是階乘的初始值,也是遞歸的終止條件。然後我們知道n!=n*(n-1)!,當n>1時,這樣我們又有了遞歸形式,又可以以遞歸演算法設計程序了。(樓上已給出譚老的程序,我就不寫了)。
我給出一種優化的遞歸演算法---尾遞歸。
從我給出的第一演算法可以看出,先進棧再出棧,遞歸的效率是很低的。速度上完全比不上迭代(循環)。但是尾遞歸引入了一個新的函數參數,用這個新的函數參數來記錄中間值.
普通遞歸階乘fac(x),就1個x而已,尾遞歸用2個參數fac(x,y),y存放階乘值。
所以譚老的程序就變成
// zysable's tail recursive algorithm of factorial.
int fac(int x, int y) {
if (x == 1)
return y;
else return fac(x-1, y*x);}
int ff(int x) {
if (x == 0)
return 1;
else return fac(x,1);}
對於這個程序我們先看函數ff,函數ff其實是對fac的一個封裝函數,純粹是為了輸入方便設計的,通過調用ff(x)來調用fac(x,1),這里常數1就是當x=1的時候階乘值了,我通過走一遍當x=3時的值即為3!來說明一下。
首先ff(3),x!=0,執行fac(3,1).第一次調用fac,x=3,y=1,x!=1,調用fac(x-1,y*x),新的x=2,y=3*1=3,這里可以看到,y已經累計了一次階乘值了,然後x還是!=1,繼續第三次調用fac(x-1,y*x),新的x=1,y=2*3=6,然後x=1了,返回y的值是6,也就是3!.你會發現這個遞歸更類似於迭代了。事實上我們用了y記錄了普通遞歸時候,出棧的乘積,所以減少了出棧後的步驟,而且現在世界上很多程序員都在倡議用尾遞歸取消循環,因為有些在很多解釋器上尾遞歸比迭代稍微效率一點.
基本所有普通遞歸的問題都可以用尾遞歸來解決。
一個問題以遞歸來解決重要的是你能抽象出問題的遞歸公式,只要遞歸公式有了,你就可以放心大膽的在程序中使用,另外一個重點就是遞歸的終止條件;
其實這個終止條件也是包含在遞歸公式裡面的,就是初始值的定義。英文叫define initial value. 用普通遞歸的時候不要刻意讓自己去人工追蹤程序,查看運行過程,有些時候你會發現你越看越不明白,只要遞歸公式轉化成程序語言正確了,結果必然是正確的。學遞歸的初學者總是想用追蹤程序運行來讓自己來了解遞歸,結果越弄越糊塗。
如果想很清楚的了解遞歸,有種計算機語言叫scheme,完全遞歸的語言,因為沒有循環語句和賦值語句。但是國內人知道的很少,大部分知道是的lisp。
好了,就給你說到這里了,希望你能學好遞歸。
PS:遞歸不要濫用,否則程序極其無效率,要用也用尾遞歸。by 一名在美國的中國程序員zysable。