How to express this mathematical relation in a c program

Question

How to create a c code that receive int parameter n and return the value of this mathematical equation

f(n) = 3 * f(n - 1) + 4,        where f(0) = 1

each time the program receive n , the program should start from the 0 to n which means in code (for loop) .

the problem here that i can't translate this into code , I'm stuck at the f(n-1) part , how can i make this work in c ?

Note. this code should be build only in basic C (no more the loops , no functions , in the void main etc) .

Answer 1

It's called recursion, and you have a base case where f(0) == 1, so just check if (n == 0) and return 1 or recurse

int f(int n)
 {
    if (n == 0)
        return 1;
    return 3 * f(n - 1) + 4;
 }

An iterative solution is quite simple too, for example if f(5)

#include <stdio.h>

int
main(void)
 {
    int f;
    int n;

    f = 1;
    for (n = 1 ; n <= 5 ; ++n)
        f = 3 * f + 4;
    printf("%d\n", f);

    return 0;
 }

Answer 2

A LRE (linear recurrence equation) can be converted into a matrix multiply. In this case:

F(0) =  |  1  |   (the current LRE value)
        |  1  |   (this is just copied, used for the + 4)

M =     | 3 4 |   (calculates LRE             to new 1st number)
        | 0 1 |   (copies previous 2nd number to new 2nd number (the 1))

F(n) = M F(n-1) = matrixpower(M, n) F(0)

You can raise a matrix to the power n by using repeated squaring, sometimes called binary exponentiation. Example code for integer:

    r = 1;             /* result */
    s = m;             /* s = squares of integer m */
    while(n){          /* while exponent != 0 */
        if(n&1)        /*   if bit of exponent set */
            r *= s;    /*     multiply by s */
        s *= s;        /*   s = s squared */
        n >>= 1;       /*   test next exponent bit */
    }

For an unsigned 64 bit integer, the max value for n is 40, so the maximum number of loops would be 6, since 2^6 > 40.

If this expression was calculating f(n) = 3 f(n-1) + 4 modulo some prime number (like 1,000,000,007) for very large n, then the matrix method would be useful, but in this case, with a max value of n = 40, recursion or iteration is good enough and simpler.

Answer 3

Best will be to use recursion . Learn it online .

Its is very powerful method for solving problems. Classical one is to calculate factorials. Its is used widely in many algorithms like tree/graph traversal etc.

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

Here you break you problem of size n into 3 instance of sub problem of size n-1 + a problem of constant size at each such step.

Recursion will stop at base case i.e. the trivial case here for n=0 the function or the smallest sub problem has value 1.