Recursive Function

Recursion allows in which a function calls itself one or more times in its body. Usually, it is returning the return value of this function call.

Termination condition:

recursion termination is when certain conditions are met and a recursive algorithm stops calling itself and begins to return values

Base condition:

if with every recursive call the solution of the problem is downsized and moves towards a base case. A base case is a case, where the problem can be solved without further recursion. A recursion can lead to an infinite loop, if the base case is not met in the calls.

Example:

4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1 Replacing the calculated values gives us the following expression 4! = 4 * 3 * 2 * 1

Generally we can say: Recursion in computer science is a method where the solution to a problem is based on solving smaller instances of the same problem. Recursive Functions in Python

Now we come to implement the factorial in Python. It's as easy and elegant as the mathematical definition. def factorial(n):

if n == 1: return 1 else: return n * factorial(n-1)

We can track how the function works by adding two print() functions to the previous function definition: def factorial(n):

print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res

print(factorial(5))

This Python script outputs the following results:

factorial has been called with n = 5

factorial has been called with n = 4

factorial has been called with n = 3

factorial has been called with n = 2

factorial has been called with n = 1

intermediate result for 2 * factorial( 1 ): 2

intermediate result for 3 * factorial( 2 ): 6

intermediate result for 4 * factorial( 3 ): 24

intermediate result for 5 * factorial( 4 ): 120

120