# Python recursive functions

(Sponsors) Get started learning Python with DataCamp's free Intro to Python tutorial. Learn Data Science by completing interactive coding challenges and watching videos by expert instructors. Start Now!

When a function call itself is knows as recursion. Recursion works like loop but sometimes it makes more sense to use recursion than loop. You can convert any loop to recursion.

Here is how recursion works. A recursive function calls itself. As you you’d imagine such a process would repeat indefinitely if not stopped by some condition. This condition is known as base condition. A base condition is must in every recursive programs otherwise it will continue to execute forever like an infinite loop.

Overview of how recursive function works

1. Recursive function is called by some external code.
2. If the base condition is met then the program do something meaningful and exits.
3. Otherwise, function does some required processing and then call itself to continue recursion.

Here is an example of recursive function used to calculate factorial.

Factorial is denoted by number followed by ( ! ) sign i.e 4!

For e.g

Here is an example

Expected Output:

Now try to execute the above function like this

You will get

This happens because python stop calling recursive function after 1000 calls by default. To change this behavior you need to amend the code as follows.

This site generously supported by DataCamp. DataCamp offers online interactive Python Tutorials for Data Science. Join over a million other learners and get started learning Python for data science today!

## 10 thoughts on “Python recursive functions”

1. pal

Have a question : When I tried above program with sys.setrecursionlimit(2008), it worked fine for print(fact(2000)), it did not work for any limit between 2001 to 2007.
Can you explain the behavior here ?

2. Mike

Hi Guru
Can you explain how this happens. With the following piece of code:

def recursion(n):
if n > 0:
print(“recursion”,n)
recursion( n-1 )
print(n)

recursion( 10 )

Which outputs the following:

recursion 10
recursion 9
recursion 8
recursion 7
recursion 6
recursion 5
recursion 4
recursion 3
recursion 2
recursion 1
1
2
3
4
5
6
7
8
9
10

How does it output the the print( n ) statement when it is not within the recursion?

3. bruce k

I am stuck on a project I want to do in python to learn python.

I created a data structure to represent a directory tree that contains a directory and file lists indexed by directory path and a subdirectory list.

I want to recursively walk the directory tree and fill out this dictionary.

How can I pass complex data structures or reference global variables in recursion?

Here is the data structure: two dicts of lists inside a dict.

tree={ directory : { “subdirlist” : subdirlist , “filelist” : filelist } }

Example: tree={ “.home/user” : { “subdirlist” : [ “subdir1”, “subdir2” ] , “filelist” : [ “file1” , “file2” ] } }

The pseudo-code would be something like this …

create_dirtree_entry( directory ):
filelist=get_file_list() <— returns a list of files in the given directory
subdirlist=get_dir_list() <— returns a list of sub-directories within the given directory
for dir in subdirlist: <— recursive call – process subdirectories then return
create_dirtree_entry( directory )
tree{ directory : { “subdirlist” : subdirlist , “filelist” : filelist } }
}

I do not understand how to add directories to the data structure from within the recursive call?

4. George Drastal

Here’s a simple recursive function that I expected would generate a list of 100 strings, from “00” through “99”. Instead, it generates the list [“0″,”00”]. Help or guidance would be appreciated.
def recurse(k):
global stack

[/crayon]

stack = []
recurse(2)
print (stack)

5. andersen

This is great!

I also found this video really helpful in explaining recursion and also the fact function

6. Ward Dejonckheere

Doesn’t seem like a good idea to up that number too much as you’ll probably run in to memory issues.
Also, the standard library “math” has a function “factorial” for factorials.
You could also rewrite the function as:
def fact(n):
fact = 1
for i in range(1,n+1):
fact = fact * i
return fact

print (“The factorial of 23 is : “,end=””)
print (fact(23))