The Self-Taught Computer Scientist. Cory AlthoffЧитать онлайн книгу.
n - 1), return n * factorial( n - 1), return n * factorial( n - 1),]
Again, your function calls itself after decrementing n by 1, but this time n is 0, which means your base case is satisfied, so you return 1 .
if n == 0: return 1
Python puts the return value on the stack again, but this time it knows what it is returning: the number 1. Now, Python's internal stack looks like this:
# Internal stack # n = 3 # n = 2 # n = 1 [return n * factorial( n - 1), return n * factorial( n - 1), return n * factorial( n - 1), 1]
Because Python knows the last return result, it can now calculate the previous return result and remove the previous result from the stack. In other words, Python multiples 1 * n , and n is 1.
1 * 1 = 1
Now, Python's internal stack looks like this:
# Internal stack # n = 3 # n = 2 [return n * factorial( n - 1), return n * factorial( n - 1), 1]
Once again, because Python knows the last return result, it can calculate the previous return result and remove the previous result from the stack.
2 * 1 = 2
Now, Python's internal stack looks like this:
# Internal stack # n = 3 [return n * factorial( n - 1), 2]
Finally, because Python knows the last return result, it can calculate the previous return result, remove the previous result from the stack, and return the answer.
3 * 2 = 6 # Internal stack [return 6]
As you can now see, calculating the factorial of a number is a perfect example of a problem you can solve by finding solutions to smaller instances of the same problem. By recognizing that and writing a recursive algorithm, you created an elegant solution to calculate a number's factorial.
When to Use Recursion
How often you want to use recursion in your algorithms is up to you. Any algorithm you can write recursively, you can also write iteratively. The main advantage of recursion is how elegant it is. As you saw earlier, your iterative solution to calculate factorials took six lines of code, whereas your recursive solution took only four. A disadvantage of recursive algorithms is that they often take up more memory because they have to hold data on Python's internal stack. Recursive functions can also be more difficult than iterative algorithms to read and debug because it can be harder to follow what is happening in a recursive algorithm.
Whether or not you use recursion to solve a problem depends on the specific situation, for example, how important memory usage is versus how much more elegant your recursive algorithm will be than a corresponding iterative algorithm. Later in the book, you will see more examples where recursion offers a more elegant solution than an iterative algorithm, like traversing a binary tree.
Vocabulary
iterative algorithm: An algorithm that solves problems by repeating steps over and over, typically using a loop.
recursion: A method of solving a problem where the solution depends on solutions to smaller instances of the same problem.
base case: A condition that ends a recursive algorithm to stop it from continuing forever.
factorial: The product of all positive integers less than or equal to a number.
Challenge
1 Print the numbers from 1 to 10 recursively.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.