Recursive Function in Python

Recursive Function in Python

Recursion is the calling of a function by itself one or more times in its body. It’s returning the return value of this function call. Recursion should be terminated at some point. Recursion should be finished when the problem is solved.

Recursion is used to browse nested data structures (for example, folders and files) or evaluate the factorial and Fibonacci series.

n! = n*(n-2)!

if n>1 and fac(1)=1

Factorial in the function:

def fact(w):

if w == 0:

return 1

else:

return w * fact(w – 1)

We have the result:

>>> fact(0)
1
>>> fact(1)
1
>>> fact(2)
2
>>> fact(3)
6
>>> fact(4)
24
>>> fact(5)
120
>>>

So it’s a true factorial.

Fibonacci series in mathematics:

fibonacci(0) = 1

fibonacci(1) = 1

fibonacci(n) = fibonacci(n –1) + fibonacci(n –2)

Fibonacciego numbers in the function:

def fib(w):

if w < 2:

return 1

else:

return fib(w-1) + fib(w-2)

We have the result:

>>> fib(0)
1
>>> fib(1)
1
>>> fib(2)
2
>>> fib(3)
3
>>> fib(4)
5
>>> fib(5)
8
>>>

Recursive function must have some condition to finish its running. It can be n == 0 or n<2. Recursive function doesn’t work fast and efficiently. If we do something wrong, we can hang the Python interpreter. Sometimes we should use while or for loops. Using sys.getrecursionlimit() i sys.setrecursionlimit(), we can get or set the maximum for the recursion depth. By default, it’s 1000, and when we exceed the limit, we will get RuntimeError exception.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s