EDIT: NOT HOMEWORK, i am trying to solve a test from past years, just learning.
I have this function, and would like to know what steps to take in order to transform it into a recursive one.
This is my function, it sums the N first odd numbers:
4^2 = 1+3+5+7 = 16;
int quadIT(int n){
int x=0;
int z=1;
int y=n;
while(y>0){
x+=z;
z+=2;
y--;
}
return x;
}
Probably the function above is not the best approach.
I would appreciate any help here.
I don't want to give you a straight answer, but rather show you roughly how to do it. These two are equivalent:
int foo(int n){
if (n == 0){
return something
} else {
do something
return foo(n-1);
}
}
while(n > 0){
do something
n--;
}
When you convert an iteration to recursion, look at the loop variable. In this case, that is your variable y. Make it a parameter of your recursive function. Next, look at other variables that change as you iterate through your loop, and make them parameters, too. At this point, you should have your function's declaration down:
int quatItRecursive(int y, int x, int z) {
...
}
Now you are ready to work on the body of your function. Start with the base case by considering the result that you get when the loop does not start (i.e. when n is zero). In this case, your function return x. So now you have your base case:
int quatItRecursive(int y, int x, int z) {
if (y == 0) {
return x;
}
...
}
To complete the body, add the recursive step, i.e. a call that performs the step of your loop. It is a recursive call now, with parameters that equal what the variables would be in the next iteration of the loop:
int quatItRecursive(int y, int x, int z) {
if (y == 0) {
return x;
}
return quatItRecursive(y-1, x + z, z + 2);
}
Finally, add a wrapper that takes a single parameter, the way your original function did:
int quantIT(int n) {
return quatItRecursive(n, 0, 1);
}
You need to break down the problem into using a reduced version of itself, plus some extra bit. In this case, the sum of the first N odd numbers is the sum of the first N-1 odd numbers plus a quantity you can calculate.
So
int sum_odd(int n)
{
if (!n) return 0;
return sum_odd(n-1) + some_calculation_here;
}
int quadIT(int n)
{
if ( n == 1 )
{
return 1;
}
else
{
return ((2*n)-1 + quadIT(n-1));
}
}
The recursive function can be defined the following way
#include <iostream>
unsigned long long quadIT( unsigned long long n )
{
return n == 0 ? 0 : 2 * n - 1 + quadIT( n - 1 );
}
int main()
{
for ( unsigned long long i = 0; i < 10; i++ )
{
std::cout << quadIT( i ) << std::endl;
}
}
The output is
0
1
4
9
16
25
36
49
64
81
Take into account that the function parameter should be defined as some unsigned integral type. Otherwise the function will be more compound.
