[PYTHON] Try to factorial with recursion

Good evening. I tried to be a beginner I hope it will be helpful to everyone.

For example, how can we achieve 3! (= 3 * 2 * 1)?

print(3*2*1)

It's done (laughs)! Then, why not write it like this using def?

test.py


def test(n:int=3):
    if n>1:
        return n * test(n-1)
    else:
        return 1

print(test())

I hurriedly tried it with the initial value of 3. For the time being, let's substitute them one by one. First, when n == 3.

test.py


# n ==When 3
def test(n:int=3):
    #n ==Since it is 3, it goes inside if
    if n>1:
       #return 3 * test(3-1)
        return n * test(n-1)
    else:
        return 1

print(test())

Hooray. I can get out because the return has arrived !! 3 * test(2) !? You can't finish without knowing test (2). There is no way. I'm not sure, but consider n == 2, that is, test (2).

test.py


# n ==When
def test(n:int=2):
    #n ==2 so go inside if
    if n>1:
       #return 2 * test(2-1)
        return n * test(n-1)
    else:
        return 1

print(test())

Hmm !? return 2 * test (1)!? Test () appears again, but this time it is test (1). It can't be helped, let's try test (1) as well.

test.py


# n ==When 1
def test(n:int=1):
    if n>1:
        return n * test(n-1)
    #n ==Since it is 1, it goes inside else
    else:
        #Returns 1
        return 1

print(test())

For the time being, when n == 1, it is return 1, so I found that the answer is 1. I'm glad I finally met an integer (laughs)

Let's organize it once. 図1.PNG After executing n == 3 as shown in the figure, n == 2 appeared, and then n == 1 appeared. As an image, 2 * test (1) is embedded in test (2), It seems that 1 * test (0) is embedded in test (1).

What we now know is that 1 * test (0) is 1 * 1, That is, it is just 1.

Alright, ignore 3 * test (2) once Let's substitute 1 * test (0) for test (1) of 2 * test (1) in the center of the figure below. 図2.PNG Since 2 * test (1) == 2 * {1 * test (0)}, we know that 2 * 1 = 2. That means. .. .. 図3.PNG 3 * test (2) == 3 * {2 * test (1)} == 3 * {2 * 1}. With this, I managed to express 3 !.

As mentioned above, when a certain event includes itself, It is said to be recursive.

Using this idea, not only 3! But also the factorial of n can be expressed, of course. It's a simple description, but it's complicated when you think about it properly. It was interesting, thank you for your hard work (≧ ▽ ≦).

Other articles
I wrote the stack in Python
Try implementing two stacks in one array in Python
Minimum value for stack made with Python(min)Add the ability to return but push/pop/min is basic O(1) !!

Recommended Posts

Try to factorial with recursion
Try to operate Facebook with Python
Try to profile with ONNX Runtime
To do tail recursion with Python2
Try to output audio with M5STACK
Try to reproduce color film with Python
Try logging in to qiita with Python
Try to predict cherry blossoms with xgboost
Try converting to tidy data with pandas
Quickly try to visualize datasets with pandas
First YDK to try with Cisco IOS-XE
Try to generate an image with aliasing
Try to make your own AWS-SDK with bash
Try to aggregate doujin music data with pandas
Try to solve the man-machine chart with Python
Try to extract Azure document DB document with pydocumentdb
Try to draw a life curve with python
Try to communicate with EV3 and PC! (MQTT)
How to try the friends-of-friends algorithm with pyfof
Try to make a "cryptanalysis" cipher with Python
Try to automatically generate Python documents with Sphinx
Try to make a dihedral group with Python
Try to make client FTP fastest with Pythonista
Try to detect fish with python + OpenCV2.4 (unfinished)
Try scraping with Python.
Convert 202003 to 2020-03 with pandas
Try to implement yolact
Try SNN with BindsNET
Try regression with TensorFlow
Try to solve the programming challenge book with python3
[First API] Try to get Qiita articles with Python
Try to make a command standby tool with python
Try to dynamically create a Checkbutton with Python's Tkinter
Try to visualize the room with Raspberry Pi, part 1
Try to solve the internship assignment problem with Python
Try to operate DB with Python and visualize with d3
Try to predict forex (FX) with non-deep machine learning
Try to make RESTful API with MVC using Flask 1.0.2
Schema-driven development with Responder: Try to display Swagger UI
[GCP] Try a sample to authenticate users with Firebase
Try to get the contents of Word with Golang
[Neo4J] ④ Try to handle the graph structure with Cypher
A sample to try Factorization Machines quickly with fastFM
Try to tamper with requests from iphone with Burp Suite
Try to automate pdf format report creation with Python
Try to specify the axis with PyTorch's Softmax function
Try function optimization with Optuna
Connect to BigQuery with Python
Try deep learning with TensorFlow
Try to build a deep learning / neural network with scratch
Try to play with the uprobe that supports Systemtap directly
Try using PythonTex with Texpad.
[Evangelion] Try to automatically generate Asuka-like lines with Deep Learning
Try to display various information useful for debugging with python
Try edge detection with OpenCV
Try implementing RBM with chainer.
Try to analyze Twitter trends
Try Google Mock with C
Try using matplotlib with PyCharm
Try programming with a shell!
Try to understand Python self