Explanation of a program using functions

Question

#include <stdio.h>

float a(int n);

main()
{
    int N;
    float z;
    puts("Dose to n (>=2)");
    scanf("%d",&N);
    z=a(N);
    printf("Gia n=%d h anadromikh sxesh dinei %f\n",N,z);
}


float a(int n)
{  
    if(n==2)
        return (7);
    else if(n==3) 
        return ((8*49-1)/1);
    else 
        return ((8*a(n-1)*a(n-1)-1)/a(n-2));


}

guys can you please explain me how this program works? i mean, if i put for example n=8 , how will it find a7,a6 etc so it get the a8 ??

It's called _recursion_. See the Wikipedia article. – Barmar Jan 23 '14 at 05:40 — Barmar, Jan 23 '14 at 05:40
In your program, the function is called recursively. – Animesh Jan 23 '14 at 10:25 — Animesh, Jan 23 '14 at 10:25

score 1 · Answer 1 · answered Jan 23 '14 at 06:14

Basically,

In C\C++ Programming the function call work on Stack Segment in Memory.See Here

and in your program you are calling function recursively.

return ((8*a(n-1)*a(n-1)-1)/a(n-2)); at this stage for input n = 8

The function all will be

for a(8)->(8*a(7)*a(7)-1)/a(6)))

for a(7)->(8*a(6)*a(6)-1)/a(5)))

for a(6)->(8*a(5)*a(5)-1)/a(4)))

for a(5)->(8*a(4)*a(4)-1)/a(3)))

for a(4)->(8*a(3)*a(3)-1)/a(2)))

for a(3) program will return (8*49-1)/1

for a(2) program will return (7)

These all function will get its own stack segment in stack memory.

And the stack segment as it works on LIFO.

the stack segment will be from Last a(8)->a(7)->a(6)->a(5)->a(4)->a(3)->a(2) and it depends on the compiler`s function calling methodology so stack segment function calling may vary. hope this will help you to understand.

score 0 · Answer 2 · 2014-01-23T09:25:15.137

When you call the function a, it either returns a value immediately for n = 2 or 3, or performs two calls of itself with n-1 and one call with n-2, then returns a value.

So:

a(2) returns immediately.

a(3) returns immediately.

a(4) calls a(3) twice and a(2) once then returns.

a(5) calls a(4) twice (each time calling a(3) twice and a(2) once) and a(3) once then returns.

a(6) calls a(5) twice (each time calling a(4) twice [each time calling a(3) twice and a(2) once] and a(3) once) and a(4) (calling a(3) twice and a(2) once) once then returns.

a(7) calls a(6) twice (each time calling a(5) twice [each time calling a(4) twice {each time calling a(3) twice and a(2) once} and a(3) once] and a(4) [calling a(3) twice and a(2) once] once) and a(5) (calling a(4) twice [each time calling a(3) twice and a(2) once] and a(3) once) once then returns.

a(8) calls a(7) twice (each time calling a(6) twice [each time calling a(5) twice {each time calling a(4) twice and a(3) once} and a(4) {calling a(3) twice and a(2) once} once] and a(5) [calling a(4) twice {each time calling a(3) twice and a(2) once} and a(3) once] once) and a(6) (calling a(5) twice [each time calling a(4) twice {each time calling a(3) twice and a(2) once} and a(3) once] and a(4) [calling a(3) twice and a(2) once] once) once then returns.

...

As you see a call causes a number of indirect calls with lower values of the argument. Fortunately, there are no infinite chains of calls, but the number of indirect calls grows exponentially with n.

This explosion can be avoided by remembering the value of a(n) when it has been computed.

Explanation of a program using functions

2 Answers2

Linked