C語言遞歸操作用法總結(jié)

更新時間：2016年02月14日 11:37:47 作者：思齊_

這篇文章主要介紹了C語言遞歸操作用法,結(jié)合實例形式總結(jié)分析了C語言遞歸操作的原理、實現(xiàn)技巧與相關(guān)應(yīng)用,需要的朋友可以參考下

本文實例總結(jié)了C語言遞歸操作用法。分享給大家供大家參考，具體如下：

用歸納法來理解遞歸

步進表達式：問題蛻變成子問題的表達式
結(jié)束條件：什么時候可以不再是用步進表達式
直接求解表達式：在結(jié)束條件下能夠直接計算返回值的表達式
邏輯歸納項：適用于一切非適用于結(jié)束條件的子問題的處理，當(dāng)然上面的步進表達式其實就是包含在這里面了。

遞歸算法的一般形式：

void func( mode)
{
 if(endCondition)
 {
  constExpression   //基本項
 }
 else
 {
  accumrateExpreesion  //歸納項
  mode=expression   //步進表達式
   func(mode)   //調(diào)用本身，遞歸
 }
}

最典型的就是N!算法，這個最具有說服力。理解了遞歸的思想以及使用場景，基本就能自己設(shè)計了，當(dāng)然要想和其他算法結(jié)合起來使用，還需要不斷實踐與總結(jié)了。

#include "stdio.h"
#include "math.h"
int main(void)
{
 int n, rs;
 printf("請輸入需要計算階乘的數(shù)n：");
 scanf("%d",&n);
 rs = factorial(n);
 printf("%d ", rs);
}
// 遞歸計算過程
int factorial(n){
  if(n == 1) {
   return 1;
  }
  return n * factorial(n-1);
}

遞歸的基本思想是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實現(xiàn)時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會產(chǎn)生無限遞歸的情況了。

能用遞歸來解決的問題必須滿足兩個條件：

① 可以通過遞歸調(diào)用來縮小問題規(guī)模，且新問題與原問題有著相同的形式。
② 存在一種簡單情境，可以使遞歸在簡單情境下退出。

如果一個問題不滿足以上兩個條件，那么它就不能用遞歸來解決。

為了方便理解，還是拿斐波那契數(shù)列來說下：求斐波那契數(shù)列的第N項的值。

這是一個經(jīng)典的問題，說到遞歸一定要提到這個問題。斐波那契數(shù)列這樣定義：f(0) = 0, f(1) = 1, 對n > 1, f(n) = f(n-1) + f(n-2)

這是一個明顯的可以用遞歸解決的問題。讓我們來看看它是如何滿足遞歸的兩個條件的：

1.對于一個n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是說規(guī)模為n的問題，轉(zhuǎn)化成了規(guī)模更小的問題；

2. 對于n=0和n=1，存在著簡單情境：f(0) = 0, f(1) = 1。

因此，我們可以很容易的寫出計算費波納契數(shù)列的第n項的遞歸程序：

int fib(n){
 if(n == 0)
  return 0;
 else if(n == 1)
  return 1;
 else
  return f(n-1) + f(n-2);
}

在編寫遞歸調(diào)用的函數(shù)的時候，一定要把對簡單情境的判斷寫在最前面，以保證函數(shù)調(diào)用在檢查到簡單情境的時候能夠及時地中止遞歸，否則，你的函數(shù)可能會永不停息的在那里遞歸調(diào)用了。

判斷一個字符串是否是回文：

function huiwen($str)
{
 if(strlen($str)==1 || strlen($str)==0){
  return 1;
 }else{
  if($str[0]==$str[strlen($str)-1]){
   $str = substr($str,1,-1);;
   echo $str."<br/>";
   return huiwen($str);
  }else{
   return 0;
  }
 }
}

希望本文所述對大家C語言程序設(shè)計有所幫助。

您可能感興趣的文章: