I always feel tall when I hear recursion , Why? ? Because I'm not familiar with it , So let's write today to remember what recursion is .

But don't worry , Let's look at a problem : seek 10 The factorial (10!).

seek x The factorial , In fact, from 1 Start to multiply one by one to x. that 10 The factorial of is 1*2*3*4*5*6*7*8*9*10

One 、 Factorial in a non recursive way

If , We don't touch recursion , How to solve such a problem ?

The simplest and rudest way direct print(1*2*3*4*5*6*7*8*9*10) The result is OK , The result is 3628800.

But this is obviously not what we want , Then you can try for In a circular way .

def factorial(n):
"""
n It's the number of the required factorial
"""
result = n
for i in range(1, n):
result *= i return result if __name__ == '__main__':
print(factorial(10))

Two 、 Factorial recursion

1. What is recursion ?

I believe everyone must have heard such a story :

 Once upon a time there was a mountain , There are temples in the mountains , There is an old monk in the temple telling a story , What are you talking about ?
Once upon a time there was a mountain , There are temples in the mountains , There is an old monk in the temple telling a story , What are you talking about ?
Once upon a time there was a mountain , There are temples in the mountains , There is an old monk in the temple telling a story , What are you talking about ?
...

In fact, this is recursion , To put it bluntly , It's about quoting yourself .

that , Recursion is used in functions , It could look like this :

def factorial():
factorial() if __name__ == '__main__':
factorial()

Calling function factorial When Continue calling... In the function factorial, Just like the story above , You can recurse endlessly ,

Until the old monk who told the story fainted , As well as the computer's memory overflow downtime .

however , One important point , Recursion is just a way to solve problems , Like factorial above , I use for It's the same as the loop .

2. Recursively solve factorial

If you want to solve the factorial problem above with recursion , You can learn more about the whole idea of recursion .

The whole idea of recursion is , Decompose a big problem into small ones , Until there's no way to break it down , therefore , Then solve the problem .

that , A recursive function has to satisfy 2 Conditions :

  • Baseline condition : The problem can be decomposed into the smallest problem , When the baseline conditions are met , Recursion is no longer going on
  • Recursive conditions : Continue to decompose the problem

    We can use this idea to try to solve the factorial problem recursively .
10! = 10 * 9! # 10 The factorial of is actually 10 * 9 The factorial 
9! = 9 * 8! # 9 The factorial of is 9 * 8 The factorial
8! = 8 * 7!
...
2! = 2 * 1!
1! = 1

You can see , Finally, it's broken down to 1 You can't continue to decompose when you're in trouble , that 1 That's the baseline condition .

def factorial(n):
# Baseline condition , When satisfied , No more recursion
if n == 1:
return 1 # Recursive conditions , When n It's not equal to 1 when , Continue to recursive
return n * factorial(n - 1) if __name__ == '__main__':
print(factorial(10))

3、 ... and 、 summary

  • recursive : It's just a way to solve problems , It doesn't have to be
  • Recursive functions : The function calls itself
  • Recursive 2 Conditions : Baseline condition ( If satisfied, there is no recursion )、 Recursive conditions ( If satisfied, the baseline recursion )
  • Recursion is like a loop : Basically, they can replace each other
  • It's easier to write loops , It's hard to read . Recursion is hard to write , But it's easy to read

【python】 Listen to me N I'm not impressed , After reading this, you will understand more related articles

  1. 【python】 The decorator heard N I'm not impressed , After reading this, you will understand

    Decorators have always been one of my " A long time ago ". This knowledge point is right there , But procrastination ... In fact, in the process of writing scripts , You may not use much of this knowledge But during the interview , This is a high frequency problem . One . What is decoration ...

  2. python( Recursive instance )

    Abstract : I'm learning python Recursive knowledge points , Always know a little , What you don't understand .. While watching the video over and over again and looking at the information , Also collect cases to analyze and verify .. Through the analysis of the following cases, I hope it can be helpful !!! 1. Using recursive method to realize factorial ... def nu ...

  3. use Python Recursion solves the problem of converting Arabic numerals to Chinese financial figures (2)-- One way to open up ideas

    A few days ago, I wrote a program to convert Arabic numerals into Chinese financial figures . Using recursion , Unfortunately, it's tree recursion . Although the actual process is unlikely to appear in the amount of large enough to let Python Recursive stack overflow , But it's always a heart disease , This thing is limited in theory after all . ...

  4. I'm doing something about NIO TCP Programming small cases encountered can not monitor write The problem of , I didn't expect it was just mine if The position of the statement is misplaced , Ah , I haven't seen it for a long time

    I'm doing something about NIO TCP Programming small cases encountered can not monitor write The problem of , I didn't expect it was just mine if The position of the statement is misplaced , Ah , I haven't seen it for a long time Post class notes : stay Java Use in NIO Go online TCP Socket programming mainly includes the following ...

  5. Python recursive _ Print node information

    Python recursive _ Print node information Recursive property :1. There has to be a clear end condition 2. Every time I go to a deeper level of recursion , The scale of the problem should be reduced compared with the last recursion 3. Recursive efficiency is not high , Too many levels of recursion can lead to stack overflow ( In the computer , When a function is called ...

  6. Python Recursively implement the Hanover tower

    Python Recursively implement the Hanover tower : def f3(n,x,y,z): if(n==1): print(x,'--->',z) else: f3(n-1,x,z,y) print(x,'--->' ...

  7. python Recursive depth first search and breadth first search algorithm simulation implementation

    One . Recursive principle small case analysis (1)# summary recursive : That is, a function calls itself , That is to say, recursion is realized Whatever circulation can do , Recursion can generally do ! (2)# Write recursive process 1. Write the critical conditions 2. Find out the relationship between this time and the last time 3. Assuming the current ...

  8. python Recursively lists all the files in the directory and its subdirectories

    python Recursively lists all the files in the directory and its subdirectories One . Preface Recursion of a function , Simply speaking , It's a function that calls itself internally Let's start with a little example , Find the factorial def factorial(n): if n == 0: return 1 e ...

  9. python recursive , Depth first search and breadth first search algorithm simulation implementation

    One . Recursive principle small case analysis (1)# summary recursive : That is, a function calls itself , That is to say, recursion is realized Whatever circulation can do , Recursion can generally do ! (2)# Write recursive process 1. Write the critical conditions 2. Find out the relationship between this time and the last time 3. hypothesis ...

  10. python Recursion times and stack overflow problems

    When doing recursion , Tested it python The recursive ability of . If you don't set the number of recursions , Probably only in 992 Times or so , There will be errors :RuntimeError: maximum recursion depth excee ...

Random recommendation

  1. SharePoint 2013 Operate the document library ECB menu

    stay SharePoint In use , We often need to customize SharePoint A series of menus , This includes ECB menu , below , Let's take a brief look at ECB How to customize the menu , And the principle . 1. Under normal circumstances, the document library ECB The menu is shown below : 2 ...

  2. Cookie And Session The difference between

    cookie Mechanism Cookies It is a small piece of text stored by the server on the local machine and sent to the same server with each request .IETF RFC 2965 HTTP State Management Mechanism It's universal c ...

  3. Python Operation file 、 Folder 、 character string

    Python String manipulation Remove spaces and special symbols s.strip().lstrip().rstrip(',') Copy string #strcpy(sStr1,sStr2) sStr1 = 'strcpy' sSt ...

  4. 149. Max Points on a Line *HARD* Find the maximum number of points on a straight line

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...

  5. MVC Small series ( 6、 ... and )【 No refresh captcha 】

    Do a no refresh captcha function : First step : First , Create a type to generate captcha in the public project ValidateCode /// <summary> /// Generate captcha object /// </summar ...

  6. Arduino Single chip microcomputer use and development problem record ( turn )

    Source :Arduino Single chip microcomputer use and development problem record 1. When uploading a program to the board Arduino IDE Tips “avrdude: stk500_getsync(): not in sync: resp=0x00” online ...

  7. readystate, asynchronous

    EventUtil.addHandler(window, "load", function(){ //create a new <script/> element. v ...

  8. vue in assets and static The difference between

    Vue Static resource management in (src Under the assets and static The difference between folders )

  9. css3d rotate

    One . Wrapping layer add -webkit-perspective: 800px; -moz-perspective: 800px; Make the subelements get 3D Results support   Two . Self sustaining subelements need to support 3D effect -webkit-t ...

  10. Cracking The Coding Interview 2.5

    The idea of this question comes from http://hawstein.com/posts/2.5.html, It's a re realization use hash To record the beginning of the cycle //Given a circular linked list, imp ...