Python Recursion


Python Recursion

Python Recursion is a technique in which a function calls itself. In other words, a function is defined in such a way that, in its body, a call is made to itself.

In this tutorial, we will learn how to write a recursion function in Python, and some of the examples where recursion is used.

Recursive Function in Python

The following code snippet is a pseudo code that illustrates a recursive function.

def myFunc():
    ...
    myFunc()
    ...

The function can have one or more arguments just like any other function in Python.

Examples

Let us go through some examples, where recursion is used.

Factorial

In this example, we will write a factorial function, that uses recursion.

Python Program

def factorial(x):
    if x < 1:
        return 1
    else:
        return x*factorial(x-1)

print(factorial(0))
print(factorial(1))
print(factorial(2))
print(factorial(3))
print(factorial(4))

Output

1
1
2
6
24

Fibonacci Series

In this example, we write a function that computes nth element of a Fibonacci series using recursion.

Python Program

def fibonacci(n):
	if n<=1:
		return n
	else:
		return(fibonacci(n-1) + fibonacci(n-2))

n = 10
fibo_series = []

for i in range(0,n):
	fibo_series.append(fibonacci(i))
	
print(fibo_series)

Output

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Summary

In this tutorial of Python Examples, we learned what Recursion is in Python, how to define a recursion function, and some examples for recursive function.