Recursive Function Tracing

Question

Consider the following recursive functions.

public static int square(int n) {

if (n == 0) return 0;

return square(n-1) + 2*n - 1;

}

public static int cube(int n) {

if (n == 0) return 0;

return cube(n-1) + 3*(square(n)) - 3*n + 1;

}

Write out the steps of the program (TRACE not run program) in order to find the value of:

1. square(5)?
2. cube(5)?
3. cube(123)?

Answer 1

Using your algebra, Simpliflies the expressions

as you go and leaves the recursion for the next step;

also shows where these formulas come from...

(n-1)^2 + 2n - 1 =

(n^2 - 2n + 1) + 2n - 1 <-- FOIL method

= n^2

going backwards:

n^2 = n^2 + 0 = n^2 + (2n-2n+1-1)

= (n^2 -2n+1) + 2n-1

= (n-1)(n-1) + 2n-1

= (n-1)^2 + 2n - 1

Square(5) = square(4) + 2*5 - 1

= square(4) + 9

= (square(3) + 2*4 - 1)+9

= square(3) + 16

= (square(2) + 2*3-1) + 16

= square(2) + 21

= square(1) + 2*2-1 + 21

= square(1) + 24

= (square(0) + 2*1-1) + 24

= square(0) + 25

= 0 + 25

= 25

And again.....

(n-1)^3 + 3n^2 - 3n + 1 =

(n-1)^2(n-1) + 3n^2 - 3n + 1 =

(n^2 - 2n + 1)(n-1) + 3n^2 - 3n + 1 = <-- FOIL method

Multiplies the polynomials

n^3 - 2n^2 + n

- n^2 + 2n - 1

3n^2 -3n + 1

=n^3

so going backwards this time, you need

the following synthetic division to show

that (n-1)^3 = n^3 - 3n^2 + 3n-1 = f(n)

which has the solution n=1

1 | 1 -3 3 -1

1 -2 1

____________________

1 -2 1 0

n^3 =

n^3 + 0

= n^3 + (3n^2-2n^2-n^2) + (n+2n-3n) + 1-1

= n^3 - 3n^2 + 3n - 1 + (3n^2 - 3n + 1)

= (n-1)(n^2-2n+1) + (3n^2 - 3n+1)

= (n-1)(n-1)(n-1) + (3n^2 - 3n + 1)

= (n-1)^3 + (3n^2-3n+1)

cube(5) = cube(4) + 3*square(5) - 3 * 5 + 1 //<--- n=5

= cube(4) + 3*square(5) - 14

= (cube(3) + 3 * square(4) - 3*4 + 1) + 3 * square(5)-14 //<-- n=4: replaces cube(4)

= cube(3) + 3*square(4) -11 + 3*square(5) - 14

= cube(3) + 3 * square(4) + 3 * square(5) - 25

= (cube(2) + 3*square(3) - 3*3 + 1) + 3 * square(4) + 3 * square(5) - 25 // <-- n=3: replaces cube(3)

= cube(2) + 3 * square(3) - 8 + 3 * square(4) + 3 * square(5) - 25

= cube(2) + 3 * square(3) + 3 * square(4) + 3 * square(5) - 33

//n=2: replaces cube(2)

= cube(1) + 3 * square(2) - 3*2 + 1) + 3 * square(3) + 3 * square(4) + 3 * square(5) - 33

= cube(1) + 3 * square(2) - 5 + 3 * square(3) + 3*square(4) + 3*square(5) - 33

= cube(1) + 3 * square(2) + 3 * square(3) + 3*square(4) + 3*square(5) - 38

//n-1: replaces cube(1)

= cube(0) + 3 * square(1) - 3*1 + 1) + 3 * square(2) + 3 * square(3) + 3*square(4) + 3*square(5) - 38

//cube(0) = 0 so it vanishes

=3 * square(1) - 2 + 3 * square(2) + 3 * square(3) + 3*square(4) + 3*square(5) - 38

//factors out the 3 from the square calls

= 3 ( square(1) + square(2) + square(3) + square(4) + square(5) ) - 40 <--- save this equation for later;

call it equation ALPHA

Now for the squaring....

square(1) = square(0) + 2*1 - 1

= 0 + 2 - 1

= 1 <--- use this for next call

square(2) = square(1) + 2*2-1

= 1 + 4 - 1

= 4

square(3) = square(2) + 2*3-1

= 4 + 6-1

= 9

square(4) = square(3) + 2*4-1

= 9 + 8-1

= 16

square(5) = square(4) + 2*5-1

= 16 + 10 - 1

= 25

plugs these into equation ALPHA

3( 1+4+9+16+25)-40 = 3(55)-40 = 165-40 = 125

=====================================================================

cube(123)

You should get 1,860,867 if it doesn't

blow up the call stack

Put an output statement in the routines and run it

using namespace std;

#include <iostream>

int square(int n)

{

cout << "square : n=" << n << endl;

if (n == 0) return 0;

return square(n-1) + 2*n - 1;

}

int cube(int n)

{

cout << "cube : n=" << n << endl;

if (n == 0) return 0;

return cube(n-1) + 3*(square(n)) - 3*n + 1;

}

int main()

{

// cout << square(5)<< endl;

// cout << cube(5)<< endl;

cout << cube(123)<< endl;

}

At least 125 pages of output!!!

1,860,867 <--- yes it is correct;

that was the output