Last active
January 8, 2016 10:09
-
-
Save giwa/6886196e034935e5e975 to your computer and use it in GitHub Desktop.
Recusive and Tail Recursive: factorial ref: http://qiita.com/giwa/items/4d9528aed2d8a2ebb8ae
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Definiation of factorial | |
# 0! = 1 | |
# n! = n * (n - 1)! | |
# | |
#|Call:1 │->│Call:2 │->│Call:3 │->│Call:4 │->│Call:5 │ | |
#│n:4 │ │n:3 │ │n:2 │ │n:1 │ │n:0 │ | |
#│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │ | |
# | |
#@profile | |
def fact(n): | |
if n == 0: return 1 | |
return n * fact(n - 1) | |
fact(20) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# e.g | |
#fact(4, 1) | |
# fact(3, 4) | |
# fact(2, 12) | |
# fact(1, 24) | |
# fact(0, 24) | |
# => return x: 24 | |
# => 24 | |
# => 24 | |
# => 24 | |
#=> 24 | |
#@profile | |
def fact(n, x=1): | |
if n == 0: return x | |
return fact(n - 1, n * x) | |
print(fact(4)) | |
# it can be rewritten like this | |
# tail recursive optimization | |
def opt_fact(n): | |
x = 1 | |
while n > 0: | |
x *= n | |
n -= 1 | |
return x | |
print(opt_fact(4)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment