### Complex recursion tracing

Hello. Anyone pls explain why I am getting 45 for this when func(12) is called

 ``1234567`` ``````int func(int x){ if(x<5) return 3*x; else return (2*func(x-5)+7); }``````
what result do you expect instead?
> Anyone pls explain why I am getting 45 for this when func(12) is called

Trace the recursive calls and you would get the explanation that you seek.

 ``1234567891011121314151617181920212223242526272829303132333435363738394041`` ``````#include #include static int depth ; static std::ostream& spacer( std::ostream& stm ) { return stm << std::string( depth*4, ' ' ) << depth << ". " ; } int func( int x ) { spacer(std::clog) << "enter function fn x == " << x << '\n' ; if( x<5 ) { spacer(std::clog) << "x<5 return 3*x == " << 3*x << '\n' ; return 3*x; } else { spacer(std::clog) << "x>=5 return 2 * func(x-5) + 7\n" ; spacer(std::clog) << "x-5 == " << x-5 << " call func(" << x-5 << ")\n" ; ++depth ; int temp = func(x-5) ; --depth ; spacer(std::clog) << "func(x-5) returned " << temp << '\n' ; int result = 2 * temp + 7 ; spacer(std::clog) << "return 2 * func(x-5) + 7 == " << result << '\n' ; return result ; } } int main() { depth = 0 ; func(12) ; std::clog << "-----------------\n" ; depth = 0 ; func(9) ; }``````

 ```clang++ -std=c++11 -stdlib=libc++ -O2 -Wall -Wextra -pedantic-errors main.cpp -lsupc++ && ./a.out 0. enter function fn x == 12 0. x>=5 return 2 * func(x-5) + 7 0. x-5 == 7 call func(7) 1. enter function fn x == 7 1. x>=5 return 2 * func(x-5) + 7 1. x-5 == 2 call func(2) 2. enter function fn x == 2 2. x<5 return 3*x == 6 1. func(x-5) returned 6 1. return 2 * func(x-5) + 7 == 19 0. func(x-5) returned 19 0. return 2 * func(x-5) + 7 == 45 ----------------- 0. enter function fn x == 9 0. x>=5 return 2 * func(x-5) + 7 0. x-5 == 4 call func(4) 1. enter function fn x == 4 1. x<5 return 3*x == 12 0. func(x-5) returned 12 0. return 2 * func(x-5) + 7 == 31```

http://coliru.stacked-crooked.com/a/7075945367f06455
1. func(12) is not less than 5 so | `return 2*func(12 - 5)+7` -> `return 2*func(7)+7`

2. func(7) is not less than 5 so | `return 2*func(7 - 5)+7` -> `return 2*func(2)+7`

3. func(2) is less than 5 so | `return 3*2` = 6

back to 2: return `2*(3*2)+7` -> `2*6+7`

back to 1: return `2*(2*6+7)+7` -> `2*19+7`

so: func(12) is the same as:
2*(2*(3*2)+7)+7 -> 2*(2*6+7)+7 -> 2*19+7 -> 45
Last edited on
You may also use a debugger to step trough your code, instead of dirtying it.
thanks all..I was not getting the return part..I was thinking it like this

2*func(12-5)+7 --> 2*7+7 this is wrong I see now..

Topic archived. No new replies allowed.