Write a program that will trace how Fibonacci numbers are generated recursively

Question

Write a program that will trace how Fibonacci numbers are generated recursively (for any N) and display the trace in the following way :

Example (N=4):

Entering level 0
        Entering level 2
                Entering level 4
                Exiting level 4
            Entering level 3
            Exiting level 3
        Exiting level 2
    Entering level 1
            Entering level 3
            Exiting level 3
        Entering level 2
                Entering level 4
                Exiting level 4
            Entering level 3
            Exiting level 3
        Exiting level 2
    Exiting level 1
Exiting level 0

Explanation / Answer

#include<iostream>

using namespace std;

void printtabs(int level){

while(level--) cout<<" ";

}

int trace(int n, int level){

printtabs(level);

cout<<"Entering level "<<level<<endl;

if (n<=1){

printtabs(level);

cout<<"Exiting level "<<level<<endl;

return n;

}else{

trace(n-2,level+2);

trace(n-1,level+1);

printtabs(level);

cout<<"Exiting level "<<level<<endl;

return n;

}

}

int main(){

int N=4;

trace(N,0);

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.