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.