閱讀(5.5k) 書(shū)簽贊(0) 我要糾錯(cuò)

C++ 遞歸函數(shù)

2018-03-24 16:36 更新

學(xué)習(xí)C++ - C++遞歸函數(shù)

C++函數(shù)可以調(diào)用自身。

這種行為稱(chēng)為遞歸。

例子


#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";
}

上面的代碼生成以下結(jié)果。

例2

演示遞歸函數(shù)階乘。


#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 ); 
}

上面的代碼生成以下結(jié)果。

例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 ); 
}

上面的代碼生成以下結(jié)果。

例4

測(cè)試迭代階乘函數(shù)。


 #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; 
}

上面的代碼生成以下結(jié)果。