python中的函數遞歸和迭代原理解析

發布時間: 2019-11-14 11:36:29 來源: 互聯網 欄目: python 點擊:

這篇文章主要介紹了python中的函數遞歸和迭代原理解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

這篇文章主要介紹了python中的函數遞歸和迭代原理解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

一、遞歸

1、遞歸的介紹

什么是遞歸?

程序調用自身的編程技巧稱為遞歸( recursion)。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法,它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算,大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說,遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。

遞歸要注意的是,它是直接或間接調用自身,所以在使用遞歸時,必須有一個明確的遞歸結束條件,稱為遞歸出口,否則,他就會陷入死循環。

尾遞歸

如果一個函數中所有遞歸形式的調用都出現在函數的末尾,我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時,這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作,這個特性很重要,因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。

python不是一門函數式編程語言,本身不支持尾遞歸(沒有對尾遞歸做優化),而且對遞歸的次數有限制,當遞歸深度超過1000時,會拋出異常,雖然可以通過sys模塊修改提柜的深度,,但是因為不是尾遞歸,仍然要保存棧,內存大小一定,不可能無限遞歸,而且無限制地遞歸調用本身是毫無意義的

import sys
sys.getrecursionlimit()
sys.setrecursionlimit(2000) # 修改遞歸深度為2000

2、遞歸的應用

遞歸分為兩個階段:回溯和遞推  
遞推 : 把復雜的問題的求解推到比原問題簡單一些的問題的求解;

回溯 : 當獲得最簡單的情況(遞歸出口)后,逐步返回,依次得到復雜的解

下面通過一個例子來分析這個過程 :

這是一個十進制轉化為二進制的函數,十進制轉化為二進制就是 將十進制不斷地除以2,直到商為0,然后將余數從后到前排列起來

def Decbin(x):
  result = ''
  if x:
    return Decbin(x // 2) + str(x % 2)
  else:
    return result
print(Decbin(7))

當我們傳入x為7時,很明顯x不為0,所以我們便進入了下次一循環,注意這時的第一層函數并沒有結束,而是一直在等待著下一層函數的返回結果。接著進入了第二層函數,參數為3,很明顯也不為0,接著又進入了第三層函數,此時第二層函數也在等待下一層函數的返回結果,以此類推,這就是遞歸函數的回溯。當我們的參數為0的時候,便會執行else的代碼,這時候函數就不再回溯,而是開始往前遞推。

二、迭代與遞歸

1、什么是迭代?

Python中的迭代是指通過重復執行的代碼處理相似的數據集的過程,并且本次迭代的處理數據要依賴上一次的結果繼續往下做,上一次產生的結果為下一次產生結果的初始狀態,如果中途有任何停頓,都不能算是迭代。常見的for循環遍歷對象就是迭代。

2、用python實現遞歸算法,代碼結構較為簡單,但效率非常低下,而迭代算法可讀性強,執行效率也非常之快。所以在運用遞歸算法時應謹慎。

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持我們。

本文標題: python中的函數遞歸和迭代原理解析
本文地址: http://www.leskzw.tw/jiaoben/python/286283.html

如果認為本文對您有所幫助請贊助本站

支付寶掃一掃贊助微信掃一掃贊助

  • 支付寶掃一掃贊助
  • 微信掃一掃贊助
  • 支付寶先領紅包再贊助
    聲明:凡注明"本站原創"的所有文字圖片等資料,版權均屬編程客棧所有,歡迎轉載,但務請注明出處。
    Pycharm創建項目時如何自動添加頭部信息VSCode中自動為Python文件添加頭部注釋
    Top 广东好彩1中奖规则