< Prev
Next >

# Python - Recursive function

Recursion is a technique by which a function calls itself from its own code. A function that can call itself from its own code is said to be a "recursive function". Using Python language, we can execute this technique and can make a function call itself to do a specific task.

To understand the technique of recursion, we will create two programs to do the same task of printing numbers from 1 to 5 in successive steps. For example -
• Printing 1 in the first line.
• Printing 1 and 2 in the second line.
• Printing 1, 2 and 3 in the third line.
• Printing 1, 2, 3 and 4 in the fourth line
• Printing 1, 2, 3, 4 and 5 in the fifth line.

In the first program, we will see a simple function(a non-recursive function) performing the task and in the second program, we will implement a recursive function doing the same task.

• ## A simple function(non-recursive) to print numbers from 1 to 5 in steps

• Let's see the first program which implements a simple non-recursive function, which has used two for loops(one nested in another) to implement the task of printing the numbers from 1 to 5 in steps, as mentioned above.

``````# Python -  A simple(non-recursive) function printing numbers from 5 to 9

# Defining a function to print numbers from 5 to 9
def steps(a):
x = a
while(x<=5):
y=1
while(y<=x):
print(y, end=' ')
y = y +1
# Calling an empty print() statement when inner while loop exits
print()
x = x + 1

# Declaring and initializing a variable to an integer value
i=1

# Calling function steps by passing it value of variable i, carrying value 1
steps(i);``````

## Output

``````1
1 2
1 2 3
1 2 3 4
1 2 3 4 5``````

In the program, we have called the print function(new in Python 3.0) with its optional end parameter initialized to an empty space i.e. ' '. By default, the value of the end parameter is a newline character \n, that's why simply calling print() function takes the cursor to the new line. which allows us to modify the ending character and

## Recursive function to print numbers from 1 to 5 in steps

Let's see the second program that implements a recursive function with the same name steps, which calls itself to print the numbers from 1 to 5 in successive steps.

``````# Python - A simple recursive function

def steps(a):
if(a<=5):
x = 1
while(x<=a):
print(x, end = ' ')
x = x + 1
print()
steps(a+1)	# Recursive function calling itself from its own code */

# Declaring and initializing a variable to an integer value
i=1

# Calling function steps by passing it value of variable i, carrying value 1
steps(i)``````

## Output

``````1
1 2
1 2 3
1 2 3 4
1 2 3 4 5``````

## Program Analysis

Let us understand our recursion program with a diagram -

As you can see in the self-explanatory diagram, the function steps() is called in successions, like -
• Starting the program, the main() function calls function steps(), which prints 1.
• Next time, the steps() function calls itself recursively for the first time, which prints 1,2
• Next time, the steps() function calls itself recursively for the second time, which prints 1,2,3
• Next time, the steps() function calls itself recursively for the third time, which prints 1,2,3,4
• Finally, the steps() function calls itself recursively for the fourth time, which prints 1,2,3,4,5

## Another example of Recursion

In the upcoming code example, we are going to find the factorial of 4, using a recursive function that calls itself.

``````# Python - Recursion example of finding factorial

def factor(a):
if(a==1):
return 1
else:
result = a * factor(a-1)    # A recursive function factor has called itself
return result

num = 4
result = factor(4)
print('Factorial of 5 is : ', result)``````

## Output

``Factorial of 4 is : 24``