## CODEX

# 7 Examples of Understanding Recursion Functions in Python

Recursion functions are functions that reuse themselves. Its general goal is to be able to solve problems that are difficult and likely to take a long time more easily. Writing code as a recursive function is actually not too complicated. However, it is an important task of an IT professional to examine this tool closer to know where to use it.

## Why Is It Important?

For those dealing with coding in general, the tasks to be automated should be performed in the best way possible. Simplicity and clarity can meet the best expectations at this stage. And using recursive functions is generally easier than using **‘for’** or **‘while’** loops.

In this article, we will not stay only on definitions or theoretical knowledge. We will also include examples that will provide a better understanding of the recursion functions. Many math functions such as the factorial or the sum of all previous numbers are good examples of this.

So let’s go!

# Example-1: Factorial

Factorials make it easier to organize sequential operations in mathematics. Examine the generally defined factorial equation below:

`n! = n * (n-1)!`

Here we have a function that is constantly decreasing and must stop somewhere. However, we can achieve this with another equation. So to concretize:

`(n-1)!=(n-1)*(n-2)! `

## Base Case

Although it gives the same result, we determine a place where we need to stop so that this process does not continue continuously. Base Case represents this point. If the value of “n” in the factorial is equal to zero, recursion now reaches the endpoint and stops repeating itself after that point.

So a recursive function will usually have the following structure:

def recursive_function(parameters): if base_case_condition(parameters): return base_case_value

recursive_function(modified_parameters)

Now let’s see how to write the factorial function as a function in Python:

`def factorial(x): `

if x == 0:

return 1

else:

return x * factorial(x-1)

If we want to see the same factorial process in another way iterative situation:

`def factorial(n):`

if n < 2:

return 1

return n * factorial(n-1)

‘Base case’ is as indicated by if in both cases. And the recursion function continues to work up to this point.

# Example-2: Calculating the Fibonacci number (up to 1000)

The calculation of the Fibonacci number can be solved as follows in a simple function created with recursion in the first place.

`def fibonacci(n): `

if n <= 2:

return 1

else:

return fibonacci(n-1) + fibonacci(n-2)

However, it is possible that there will be a time problem when trying this code for multiple numbers. Maybe you will strain your machine a little. This is because the previous ones are recalculated in obtaining each fibonacci number. Fibonacci (4) and fibonacci (3) for fibonacci (5), fibonacci (3) and fibonacci (2) for fibonacci (4), fibonacci (2) and fibonacci (1) for fibonacci (3). So: “The processor is overburdened” and you’re trying to get from the complex to the less complex.

Alternatively, we can develop a solution with the iterative function as follows, and we prefer to make it easier than less complex:

`def fib_faster(n, past=1, current=1): `

if n <= 2:

return current

else:

return fib_faster(n-1, current, past+current)

With the parameter n, we determine how many operations will be performed to find the next term. You need 1 term for the 3rd term, 2 times for the 4th term, 3 times for the 5th term. Since the first two terms are accepted from the outset, there will always be +2 terms.

Note:Python has a depth limit of 1000 for recursive functions. So this means you have a limit on term sum for you. You won’t be able to return any more. Just way to F1000 (thousandth term of fibonacci_number) :)

# Example-3: Finding the sum up to the number itself

As we stated in the beginning, recursion calls itself again. Here, too, we will try to show all numbers before a number, which we will denote with n, like a sum. So let’s set the function below and get the sum of the numbers up to 10:

def print_sum(number):

if number==1:

return 1

else:

return number+print_sum(number-1)

print(print_sum(10))output:

55

# Example-4: Showing the characters in the word from beginning to end

We will define a function that reads the same characters in a word one by one from left to right and prints None with the base_case point at the end of the word. We will use the ** len ()** function for this.

def print_character(word, length):

if length == len(word)-1:

print(word[length])

else:

print(word[length])

print_character(word, length + 1)word = "Python"

print(print_character(word, 0))output:

P

y

t

h

o

n

None

# Example-5: Adding the elements of a number array

To get the sum of the lists and the elements, let’s call each backward and create the **sum_list** function.

def sum_list(lst,length):

if length==0:

return lst[0]

else:

return lst[length]+sum_list(lst,length-1)lst=[1,2,3,4,5]

print(sum_list(lst,len(lst)-1))output:

15

# Example-6: Calculating positive divisors of a number

We will write a function that expresses numbers by dividing them by their divisors. The number that we will specify in the function will be divided by the numbers from 1 to the number itself. However, we do not want the remainder of this section. For this, if we take 12 for example, we expect 1,2,3,4,6,12 to be returned. At the end of the function will return the number itself. In that case function:

def positive_divisor(number,i):

if number%i==0:

print(i)

elif number==i:

return number

return positive_divisor(number,i+1)print(positive_divisor(63,1))output:

1

3

7

9

21

63

# Example-7: Returning subsets of a list set

This can be seen as perhaps the most complex example. Returns the different combinations of elements that make up a list according to the definition of subsets on the subject sets, which are also known in mathematics. For this reason, two different key functions need to be coding.

**First:** With ‘Add elements’ we will make sure that certain elements or elements to the internal list are added to an existing list. For this, we need an element to be added and a list.

**Second:** With ‘Show subsets’ we will continue to rotate different lists, including the addition of elements until it reaches the base case point.

So for the ‘add_elements’ function first:

def add_elements(e, lst): # adds the element to each list in the lst

if lst == []:

return []

else:

return [lst[0] + [e]] + add_elements(e, lst[1:])print(add_elements('add',[['a'],['d'],['d']]))output:[['a', 'add'], ['d', 'add'], ['d', 'add']]

Now let’s list the subsets of our sample set by combining our function showing the subsets with the above function.

Note:The empty set is a subset of each set. Therefore, it is an important tip for the base case.

We will represent the empty set with [].

So base_case is equal to: lst == []

With formula → 2 ** number of elements

def show_subsets(lst):

if len(lst) == 0:

return [[]]

else:

return show_subsets(lst[:-1]) + add_elements(lst[-1], show_subsets(lst[:-1]))print(sorted(show_subsets(["x","y","z"])))output:

[[], ['x'], ['x', 'y'], ['x', 'y', 'z'], ['x', 'z'], ['y'], ['y', 'z'], ['z']]

# Conclusion

We examined 7 different examples to better understand the recursion functions in Python. The purpose of this article was to include applicable functions. I hope it became easier to understand the ideal functions for calculations, many of which are not unfamiliar to those already involved in mathematics.

Thank you for reading!

## References

(1): Source for the picture used in the created image: https://commons.wikimedia.org/wiki/File:FibonacciSpiral.svg