Example of Python's recursion-based algorithm implementation of the Hannauta and Fibonacci series

This article example describes Python based recursive algorithm implementation of the Hannover Tower and Fibonacci series. Shared for your reference, as follows:

Here we learn the use of recursion in python with 2 examples.

1. Find the number in the Fibonacci series with subscript n (counting from 0).

The Fibonacci series has the form 0,1,1,2,3,5,8,13 ......

① Use while loop, python2 code is as follows:

def fib(n):
  a,b=0,1
  count=0
  while count<n:
    a,b=b,a+b
    count=count+1
  print a

The results of the run are as follows:

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5

② Use recursion (recursion must have boundary conditions), python2 code is as follows:

def fib(n):
  if n==0 or n==1:# Recursive boundary conditions
    return n
  else:
    return fib(n-1)+fib(n-2)

The results of the run are as follows:

>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5

Recursion is one of the algorithms that best expresses computational thinking, so let's look at the execution of recursion using f(4) as an example:

In the same program, although using recursion is a concise program, the execution efficiency of recursion is lower than that of loops, and the resource consumption of the system is greater than that of loops. Because recursion is called one layer at a time and returns one layer at a time at the end of the program, the execution efficiency of recursion is not high. So why use recursion at all? Because there are some problems where we can't find a very obvious loop solution, but it's easy to find an obvious recursive solution. Take for example the famous Hannauta problem.

2. Hannover Tower

Below is a simplified version of the Hannukah Tower game with only 4 plates:

The rules for the game of Hannukah are as follows:

The python2 code is as follows:

def hanoi(a,b,c,n):
  if n==1:# Recursive end conditions
    print a,'->',c
  else:
    hanoi(a,c,b,n-1)
    print a,'->',c
    hanoi(b,a,c,n-1)

Run results:

>>> hanoi('A','B','C',1)
A -> C
>>> hanoi('A','B','C',2)
A -> B
A -> C
B -> C
>>> hanoi('A','B','C',3)
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

Readers interested in more Python related content can check out this site's topic: thePython Data Structures and Algorithms Tutorial》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniques》、《Python introductory and advanced classic tutorialsand theSummary of Python file and directory manipulation techniques》

I hope that what I have said in this article will help you in Python programming.