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 non-recursive function
performing the above mentioned task, and in the second program, we will implement a recursive function to do the same task.
A simple non-recursive function to print numbers from 1 to 5 in steps
In the upcoming program we will implement a simple non-recursive function, which has used two for-loops(one loop nested in another)
to implement the task of printing the numbers from 1 to 5 in steps.
# 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 being 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 the print() function takes the cursor to the new line.
Advertisement
Recursive function to print numbers from 1 to 5 in steps
In the next program we will implement a recursive function with the
same name, steps, as our previois program. This function 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 the steps() function, 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 next example of a recursive function, we are going to find the factorial of 4 by 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)
