Complex recursion tracing

[csstudent123]

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

int func(int x){
	if(x<5)
		return 3*x;
	else
		return (2*func(x-5)+7);
	
	}

[LaboPie]

what result do you expect instead?

[JLBorges]

> 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.

#include <iostream>
#include <string>

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

[GaiusBaltar]

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

[ne555]

You may also use a debugger to step trough your code, instead of dirtying it.

[csstudent123]

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..