# DSA: Recursion In Programming, we have a concept that is super important when we deal with the implementation of trees and graph data structure and it is called recursion. Recursion is a technique offered by many programming languages in which a user-defined function can call itself again and again until a base condition gets satisfied. If a user-defined function calls another user-defined function then it is called indirect recursion. A function is called a recursion function only if it calls itself. A recursive function acts like an iterative statement such as for loop, but using a recursive function can require more memory than an iterative statement and implementing a recursive statement is complex than an iterative one.

The syntax for Recursion:

```def function(arg):
#some statement
#base condiition
function()```

Recursion Example in python:

```def print_n_to_1(n):
if n==1:
print(1) # base condition
else:
print(n)
print_n_to_1(n-1)

print_n_to_1(10)```

Output:

```10
9
8
7
6
5
4
3
2
1```

### Properties of a Recursion Function

While creating a recursion function, we should take care of some recursive properties, or else we could get stuck in the infinite recursive call, which is similar to an infinite loop. So, while writing a recursive statement, make sure your function must have these two properties.

• Base condition
• Progressive approach.

#### Base Condition

The recursive function must have a Base condition that returns a single value or terminate the function, rather than calling the function again and again. In the above example, we have provided a base condition that executes if n==1: and it terminates the function and stops the recursive call. If we did not provide a base condition in the above example, the recursive call would get an infinite approach.

Example:

 Recursion with the base condition Recursion without base condition ```def print_n_to_1(n):    if n==1:        print(1) # base condition    else:        print(n)        print_n_to_1(n-1) print_n_to_1(10)``` ```def print_n_to_1(n):    print(n)   print_n_to_1(n-1) print_n_to_1(10)``` Output ```10 9 8 7 6 5 4 3 2 1``` ```10 9 8 7 6 5 4 3 2 1 0 -1 … ………```

#### Progressive approach

The recursive call should be written in such manner, so for each recursive call, we get closer to the base condition. In the above example when we are performing the recursive call, we calling the print_n_to_1(n-1) statement which decrementing the value of n for each recursive call. If we do not perform a Progressive approach in a recursive function we could get stuck in an infinite recursive call. Example:

 Recursion with Progressive approach Recursion without Progressive approach ```def print_n_to_1(n): if n==1:    print(1) # base condition    else:    print(n)      print_n_to_1(n-1) # With progressive approch print_n_to_1(10)``` ```def print_n_to_1(n): if n==1:    print(1) # base condition    else:        print(n)       print_n_to_1(n) #without progressive approach. print_n_to_1(10)_1(10)``` Output ```10 9 8 7 6 5 4 3 2 1``` ```10 10 10 10 10 10 10 … ………```

#### Recursion Implementation

Mostly all programming languages use a stack to implement the recursive calling. In general, when a function A calls function B, the control of execution transfer from A to B , the function A get on hold and the execution of function B get started. Once the function B gets completely executed the control of execution goes back to the function A and the execution resume where it was in the hold.

Example:

```Normal Function calling:

function A(n):
B(n++) # go to function B()
# do something

function B(x):
#do something with x once done get back to A()

A(n) ------Pause A(n++)------> B(n++) --------Resume A(n++)------> A(n++)```

The same criteria apply for the recursive functions, but here instead of transferring execution control from function A to B, the execution control transfer from function A to function A with different data set.

For example:

```function A(n):
A(n++) # call function A() with n++ argument

A(n) ----------pause A(n)----->A(n++) ----------pause A(n++)----->A(n++++)```

#### Why use Recursion

This is a valid question, we have iterators such as loops, for repetitive statements so why use Recursion? The answer is simple. Recursive provides a more readable and simple way to write code, in tree traversal iterators such as for loop are not that much efficient that’s why we use recursive statements over iterators.