C++ 递归函数

学习C++ – C++递归函数

C++函数可以调用自身。

这种行为称为递归。

例子

#include <iostream>
using namespace std;

void countdown(int n);
int main(){
    countdown(4);           // call the recursive function
    return 0;
}

void countdown(int n){
    cout << "Counting down ... " << n << endl;
    if (n > 0)
        countdown(n-1);     // function calls itself
    cout << n << "\n";
}

上面的代码生成以下结果。

例2

演示递归函数阶乘。

#include <iostream> 
#include <iomanip> 
using namespace std; 

unsigned long factorial( unsigned long ); // function prototype 

int main() 
{ 
    // calculate the factorials of 0 through 10 
    for ( int counter = 0; counter <= 10; ++counter ) 
        cout << setw( 2 ) << counter << "! = " << factorial( counter ) 
           << endl; 
} // end main 

// recursive definition of function factorial 
unsigned long factorial( unsigned long number ) 
{ 
    if ( number <= 1 ) // test for base case 
        return 1; // base cases: 0! = 1 and 1! = 1 
    else // recursion step 
        return number * factorial( number - 1 ); 
}

上面的代码生成以下结果。

例3

// Testing the recursive fibonacci function. 
#include <iostream> 
using namespace std; 

unsigned long fibonacci( unsigned long ); // function prototype 

int main() 
{ 
    // calculate the fibonacci values of 0 through 10 
    for ( int counter = 0; counter <= 10; ++counter ) 
       cout << "fibonacci( " << counter << " ) = " 
           << fibonacci( counter ) << endl; 

    // display higher fibonacci values 
    cout << "fibonacci( 20 ) = " << fibonacci( 20 ) << endl; 
    cout << "fibonacci( 30 ) = " << fibonacci( 30 ) << endl; 
    cout << "fibonacci( 35 ) = " << fibonacci( 35 ) << endl; 
} // end main 

// recursive function fibonacci 
unsigned long fibonacci( unsigned long number ) 
{ 
    if ( ( number == 0 ) || ( number == 1 ) ) // base cases 
       return number; 
    else // recursion step 
       return fibonacci( number - 1 ) + fibonacci( number - 2 ); 
} 

上面的代码生成以下结果。

例4

测试迭代阶乘函数。

 #include <iostream> 
 #include <iomanip> 
 using namespace std; 

unsigned long factorial( unsigned long ); // function prototype 

int main() 
{ 
    // calculate the factorials of 0 through 10 
    for ( int counter = 0; counter <= 10; ++counter ) 
        cout << setw( 2 ) << counter << "! = " << factorial( counter ) 
            << endl; 
} // end main 

// iterative function factorial 
unsigned long factorial( unsigned long number ) 
{ 
    unsigned long result = 1; 

    // iterative factorial calculation 
    for ( unsigned long i = number; i >= 1; --i ) 
        result *= i; 

    return result; 
}

上面的代码生成以下结果。