also depend on the algorithm we choose. It can happen that

if a proper algorithm is not chosen, it may take a very long

time for execution.

On writing a simple recursive fibonacci generator function for

the nth element,

*fib(n)*, we will get fine results, but only for low

values of

*n*. This is because

*fib(n)*has exponential complexity.

Such functions grow very fast, so fast that even for small

values of `n' (where `n' is the size of the input), our program

will take a long time to finish.

Memoization is the process by which we speed up the situation.

The underlying principle is to create an associative array, say

*dict*, which contain keys = n, and values =

*fib(n)*. Each time a

*fib(n)*is called, the associative array will be checked whether it

contain the key 'n'. If yes, just return

*dict[n]*. Otherwise, create

a new key: value pair for

*dict*. Thus, the number of recursion will

be drastically reduced, with this look-in-the-lookup-table policy.

Ofcourse, memoization is an upgrade to time compplexity, but

will consume space.

The implementation in Python looked like:

*def memoized_fib(x):*

if dict.has_key(x):

return dict[x]

else:

dict[x] = fib(x)

return dict[x]

def fib(n):

if n == 0: return 0

elif n == 1: return 1

else: return memoized_fib(n-2) + memoized_fib(n-1)

dict = {0: 0, 1: 1}

if dict.has_key(x):

return dict[x]

else:

dict[x] = fib(x)

return dict[x]

def fib(n):

if n == 0: return 0

elif n == 1: return 1

else: return memoized_fib(n-2) + memoized_fib(n-1)

dict = {0: 0, 1: 1}

In Python, the

**recursion limit**is fixed by the interpreter itself. It can

be found in:

**sys.setrecursionlimit(<limit>)**Now, set a very high limit, and run the code. If its high enough, u will

deplete the stack memory size (8 MB) of the C backend of your Python

virtual machine, leading to a segmentation fault there, which is

propagated back to your Python interpreter,

**crashing Python itself**!

## No comments:

## Post a Comment