Geek Answers Handbook

Recursive functions in C / C ++

Looking at a recursive function in C / C ++, are they useful in any way? Where exactly are they mainly used? Are there any advantages in terms of memory with recursive functions?

Edit: is recursion better or is the while loop used?

+5
source share
10 answers

Recursive functions are mainly used to facilitate the development of algorithms. For example, you need to go through a directory tree recursively - limit its depth, so you will most likely never come across something like a too deep recursion and the subsequent one, but it is much easier to write a reverse tree path recursively and then do the same iterative way.

In most cases, recursive functions do not save memory compared to iterative solutions. Even worse, they consume stack memory, which is relatively small.

+10
source

they have many uses, and with them some things become very difficult impossible. for example, iterate trees.

+4
source

. .

C . , , . C/++. !

, - , , , C/++. , , . , , , !

PS: , . , , /.

+4

QuickSort , , .

+3

, , . .

unsigned greatest_common_divisor_iter(unsigned x, unsigned y)
{
    while (y != 0)
    {
        unsigned temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

unsigned greatest_common_divisor(unsigned x, unsigned y)
{
    return y == 0 ? x : greatest_common_divisor(y, x % y);
}

. , x y const, .

+2

(, ), , while. , , ( ).

Tom / , , C, . C.

+1

- , , (, - ), - , , . , .

+1

, , , (, Scheme) , , , , .

, Scheme, C/++ .

+1

, :

  • (, )
  • ( , )

, .

0

.

, :

 factorial(0) = 1
 factorial(n) = n * factorial(n-1)

, .

The recursive version and recursive relation defined above look the same and therefore easier to read.

Recursive:

double factorial ( int n )
{
 return ( n ? n * factorial ( n-1 ) : 1 );
}

Cycle:

double factorial ( int n )
{
 double result = 1;
 while ( n > 1 )
 {
  result = result * n;
  n--;
 }
 return result;
}

One more thing:

The recursive version of the factorial includes a tail call for itself and can be optimized using a tail call. This brings the spatial complexity of the recursive factorial up to the spatial complexity of the iterative factorial.

0
source

More articles:


All Articles