36 recursion

36.1 Real life example 1

Russian dolls are good example for recursion.

36.2 First example

Recursive functions calls itself.

def recursive(x):
    # do something
    x = x - 1
    print(x)
    recursive(x)

But this way without any exit condition will lead to error. See below.

In [1]: def recursive(x):
   ...: ^I# do something
   ...: ^Ix = x - 1
   ...: ^Irecursive(x)
   ...:

In [2]: recursive(10)
10
9
..
-2968
-2969
-2970
-2971
-2972
-2973
-2974
-2975
-2976
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-2-88ae67f210a8> in <module>
----> 1 recursive(5)

<ipython-input-1-c9aaee61b136> in recursive(x)
      3         x = x - 1
      4         print(x)
----> 5         recursive(x)

... last 1 frames repeated, from the frame below ...

<ipython-input-1-c9aaee61b136> in recursive(x)
      3         x = x - 1
      4         print(x)
----> 5         recursive(x)

RecursionError: maximum recursion depth exceeded while calling a Python object

We need to add an exit condition to our function. This is sometimes called base case, function returns no value or return a default value effectively exiting.

def recursive(x):
    # do something
    x = x - 1
    print(x)
    if (x > 0):
        recursive(x)
    # else do nothing, exit from function

Then, a recursive function will have following structure.

def recursive(parameters):
    if check parameters:
        # exit or return
        return base_case_value
    # modify parameters here and call itself again
    recursive(modified_parameters)

36.3 Recursive Function structure

A recursive function is a function that calls itself.

we have function that call itself
we have an exit condition
we should somehow change our input variables so that exit condition will eventually be TRUE.

36.4 pseudo code 1

if exit_condition_true:
    exit function
else:
  change input variable
    call itself again

36.5 pseudo code 2

if not exit_condition_true:
  change input variable
    call itself again
else:
    exit function

See following stackoverflow question

36.6 Examples

36.6.1 Factorial

Factorial example used widely for recursion but it is not a good example in my opinion since it could be easily solved with loops also.

36.6.2 Fibonacci

36.6.3 Tree structures

Most tree structures. For example going through a family tree and searching files in operating system.

36.6.4 Files in a folder

getting list of files and directories in a given directory and going deeper in existing directories to search for a given text or filename. Consider a folder in operating system. Starting from a this base folder, print names of all files in this folder. If this folder contains sub folder, you need also print file names in sub folder too. This should go recursively.

This is a better example for recursion since it is not easily solved with loops. In general, any tree structure are more easily solved using recursion.

36.6.5 More reading for recursion

36.7 Links in our references

Non-Programmer’s Tutorial for Python 3/Recursion