Creative Commons License
This blog by Tommy Tang is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

My github papge

Saturday, March 30, 2013

recursion in python

I just finished watching the MIT open course on python lecture 4

It talks about recursion at the end which I find is really interesting.

Two examples the professor gave are 
1. check a string is a palindrome or not.
2.  Return the Fibonacci number of x.

python code:

def is_palindrome(s):
    if len(s) <= 1;
         return True
          return s[0]=s[-1] and is_palindrome(s[1:-1])

def fib(x):
    if x==0 or x==1 :
          return 1
          return fib(x-1) + fib(x-2)

There are many algorithms to solve the first problem, but the pythonic way would be:
def is_palindrom_v2(s):
     return s==s[::-1]

#simply reverse the string and check if it is the same as the original one.

update 06/13/13:
it is very expensive for recursion in python in terms of computing time.
watch Lesson 6 here:!/c-cs101/l-48756019/m-48532681


No comments:

Post a Comment