Lesson 022: function: recursion is god horse after class test questions and answers

Test questions ：

0. How does recursion behave in programming ？

answer ： In programming , Recursion is a behavior of the function call itself .

1. Which two basic conditions must recursion satisfy ？

answer ：

One 、 Function call itself

Two 、 Set the correct return condition

2. Think about it , According to the recursive nature , Is there any case where recursion has to be used in programming ？

answer ： Like the tower of Hanoi , indexes （ Because you never know if there is a directory in this directory ）, Quick sort （ One of the top ten algorithms in the 20th century ）, The definition of tree structure, etc. if recursion is used , You can do more with less , Otherwise, the program cannot be implemented or is quite difficult to understand .

3. Using recursion to compute factorial problems or Fibonacci sequences is a bad algorithm , Do you know why ？

answer ： The little turtle said at the beginning of the course “ Ordinary programmers use iteration , Talented programmers use recursion ” This sentence is reasonable .

But don't get it wrong , Not that I can use recursion , Replace everything that can be iterated with recursion “ Talented programmer ” 了 , On the contrary , If you really do this , Then you are “ Tortoise programmer ” La .

Why do you say that ？ Don't forget to , The implementation of recursion can be that the function calls itself , Every time a function is called, you need to press the stack 、 Bomb stack 、 Stack operations to save and recover registers , So it's very time and space consuming up here .

in addition , If recursion forgets to return , Or the return condition is set incorrectly , Then executing such recursive code will become a bottomless hole ： Can't get in ！ So when writing recursive code , Remember the pithy formula ： Recursive recursion , I'm going home! ！ Come out to mix , One day it will have to be paid back ！

4. Please talk about the advantages and disadvantages of recursion （ No official statement is required , You can write what you think ）

answer ：

advantage ：

1） The basic idea of recursion is to transform large-scale problems into small-scale problem combinations , So as to simplify the difficulty of solving the problem （ For example, Hanoi tower game ）.

2） Some problems use recursion to make the code simple and easy to understand （ For example, you can easily write a recursive algorithm for traversing binary trees in the first, middle and last order , But if you want to write the corresponding non recursive algorithm, it is not something that beginners can do .）

shortcoming ：

1） Because the principle of recursion is that the function calls itself , So once a large number of functions are called, the space and time consumption is “ Extravagant ”（ Of course Ferrari is also extravagant , But many people are still flocking to it ）.

2） It is easy for beginners to set the return condition by mistake , Causes recursive code to call endlessly , Final stack overflow , Program crash .

5. Take a picture with your mobile phone “ Recursive selfie ”

answer ： Shoot in the mirror

use one's hands ：

0. Write a... Using recursion power() Function simulation built-in function pow(), namely power(x, y) To calculate and return x Of y The value of the power .

def power(x, y):
    if y:
        return x * power(x, y-1)
    else:
        return 1
    
print(power(2, 3))

1. Write a function using recursion , Use Euclidean algorithm to find the greatest common divisor , for example gcd(x, y) The return value is a parameter x And parameters y Maximum common divisor of

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
    
print(gcd(4, 6))