Dart Recursion

Recursion is one of the most important and interesting concepts in any programming language. It can be defined as a process in which a function calls itself directly or indirectly. It is used to solve large complex problems by breaking them into smaller subproblems.

Recursion can be of two types :

1. Direct Recursion – In this type of recursion, a function calls itself from within itself.
2. Indirect Recursion – In this type of recursion, a function calls another function and vice - versa.

In recursion, the recursive function calls itself repeatedly until a base condition is reached and stops calling when it evaluates to false. The function basically has two parts.

Recursive: The recursive part of the function is called again and again with a smaller subproblem.

Base: The base condition is a Boolean condition which is checked every time a function call is made. If the function is in a base condition it is used to provide a solution.

A function can be made recursive only if:

1. The function can be defined in terms of itself.
2. The function must have a definite terminating condition.
3. Every recursive call to the function must take it closer to the terminating condition.

Recursion uses Recursion stack to store the resultant value of the subproblems to be later returned to the main problem. Execution of the call statement every time results in some outcome value that is pushed in stack. When the base condition is reached, back-tracking begins and all the numbers are popped out of the stack.

Syntax:

void func_name( )
{
    // Base code . . . .
    func_name( ) ;
    // Some code...
}
void main( )
{
    func_name( ) ;
}

Consider the following code in Dart that prints the factorial of the number using the concept of recursion.

Program

import 'dart:io';
int recur( int n ) {
  int fact = 1 ;
  if ( n == 1 )
    return 1 ;
  else
    fact = n * recur( n – 1 ) ;
  return fact ;
}
int main( ) {
  print( ' Enter the number of which you want to find the factorial :  ' ) ;
  int? n = int.parse( stdin.readLineSync( ) ! ) ;
  int fact = recur( n ) ;
  print( ' \n Factorial of the number is : $fact ' ) ;
  return 0 ;
}

Output :

Enter the number of which you want to find the factorial :
5


Factorial of the number is : 120

Explanation :

Consider the above code in Dart that prints the factorial of the number 5 which is 120. The function recur (int n) accepts one argument n of integer type and return type of integer which signifies that the function returns an integer value.

If the value of n is 1, then simply return 1 because the factorial of 1 is 1 only. Else if n is any number other than 1 the function recursively calls itself and stores the temporary product in ‘fact’ variable. This recursive call is made till n is 1.

The computation takes place as follows :

First call :       when n = 5

                        fact = 5 * recur( 4 )

                        5 goes in recursion stack.

recur( int n ) function is called again.

Second call :   n = 4

                        fact = 4 * recur ( 3 )

                        4 goes in recursion stack.

recur( int n ) function is called again.

Third call :     n = 3

                        fact = 3 * recur ( 2 )

                        3 goes in recursion stack.

recur( int n ) function is called again.

Fourth call :   n = 2

                        fact = 2 * recur( 1 )

                        2 goes in recursion stack.

Since in the next call, n becomes 1, 1 is returned.

In the case of Recursion, the recursive call every time should take it closer to the terminating condition as the problem has to be terminated to return a final result.  If the base condition is not set properly or the function isn't defined in its term properly, the problem does not terminate. This leads to an infinite loop.

As explained earlier these function calls use stack memory to store the temporary values. This definitely takes up a lot of memory. The function can cause stack overflow if the base condition is not defined or unable to reach. This condition is called as Terminating condition in Recursion.

Advantages of using Recursion:

• The solution of the problem using recursive function is concise and easy.
• Recursive functions are prominently used with the problems related to data structures such as trees and graphs.
• Recursion reduces the time complexity of the algorithm.
• Recursion reduces the unnecessary calling of the same function with same lines of code again and again.

Disadvantages of using Recursion:

• Recursion consumes a lot of memory.
• The recursive functions are computationally exhaustive.
• It is hard to debug the code.
• They are not always very useful.

Consider another example of Dart recursive function to get the better understanding of the topic:

Program:

// function to print the nth Fibonacci number 
int Fib( int n )
{
  if( n <= 1 ) // terminating condition 
    return n ;
  else
  return Fib( n - 1 ) + Fib( n - 2 ) ; // recursive call to the function
}
void main( ) 
{
  int n = 10 ;
  print( ' nth Fibonacci number is : ' ) ;
  int fib = Fib( n ) ; // calling the function fib( n )
  print( fib ) ;
}

Output :

nth Fibonacci number is : 
55

Explanation :

Consider the above code in Dart that prints the nth Fibonacci number, here n is 10 and the Fibonacci number at the 10^th place is 55. The function Fib( int n ) accepts one argument n of integer type and return type of integer which signifies that the function returns an integer value. The value of n is 1, then simply return n. Else if n is a number more than 1, then the function recursively calls itself and returns the temporary sum. This recursive call is made till n is 1.