Art111111
Badges: 11
Rep:
?
#1
Report Thread starter 2 years ago
#1
http://www.wjec.co.uk/question-bank/...9-cdaf3864442d


I don't understand this question. The mark scheme seems as though the program loops but there is no way for it to loop.
If anyone can understand I would appreciate a better explaination.
0
reply
winterscoming
Badges: 19
Rep:
?
#2
Report 2 years ago
#2
The function is an example of Recursion. Recursion is a type of repetition where a function "calls itself".

Understanding how recursion works requires that you understand what happens in memory when a function is called. Calling a function isn't simply a matter of moving an instruction pointer, when a function is called a whole new "stack frame" is created.

The reason this is important, is that a function "calling itself" is NOT behaving like a JUMP or GOTO statement, because jump/goto statements don't create a new frame on the stack.

A "stack frame" is a memory space which stores a set of variables for the scope of a function. In the particular case of the fibonacci function shown in that exam question, the stack frame contains a variable called Num.

If you want to visualise recursion, then one way to do it would be to 'unroll' the function and mimic the effect of multiple stack frames using hard-coded values instead.

So consider the way that the fibonacci sequence itself is calculated for Num = 4 , except using an "unrolled" non-looping, non-recursive set of functions instead:
Code:
function fibonacci4() : integer
    return fibonacci3() + fibonacci2()

function fibonacci3() : integer
    return fibonacci2() + fibonacci1()

function fibonacci2() : integer
    return 1

function fibonacci1() : integer
    return 0
Just to be clear, the above example is not recursion, because none of those functions are calling themselves; but it is a pseudocode illustration of what happens to the flow of a program when you "unroll" the recursive fibonacci function by-hand. i.e. fibonacci4() is calling the fibonacci3()and fibonacci2()functions, etc.

By re-writing the above example using recursion, you would end up with a single fibonacci(Num)function which "calls itself" but essentially performs exactly the same number of function calls, in exactly the same pattern, and performs exactly the same calculation at the end.

So, in a recursive fibonacci(Num) function, a call to fibonacci(Num=4) would call fibonacci(Num=3) and fibonacci(Num=2) - the reason that the effect of this is the same as the un-rolled function is that a new stack frame is created every time the fibonacci function is called, and the stack will contain many frames, each with a different Num variable.

If it helps, try implementing the recursive function, and then its un-rolled equivalent in a programming language of your choice, to see how it works, and check the flow of the program, setting breakpoints to see step-by-step what's actually happening.

Does this make the concept clearer?
0
reply
Art111111
Badges: 11
Rep:
?
#3
Report Thread starter 2 years ago
#3
Yes thanks.
When it said recursion all i was thinking was do loops or while loops.
0
reply
winterscoming
Badges: 19
Rep:
?
#4
Report 2 years ago
#4
(Original post by Art111111)
Yes thanks.
When it said recursion all i was thinking was do loops or while loops.
Yeah, Recursion is a more complex and less obvious type of repetition due to the involvement of stack frames. Most forms of repetition are iterative rather than recursive.

Iterative loops such as for, foreach, while and do..while are generally compiled directly down into a goto or jump/branch instruction. (i.e. at the lowest level when you're looking at assembly language or raw machine code) - this makes them fairly easy to trace and visualise.

In general, most people find recursion more difficult to trace because it potentially results in a lot of simultaneous branches and stack frames; there's a much higher cognitive load for your brain to process when looking at recursion compared with the other simple loops where you can usually just look at each iteration on its own.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Regarding Ofqual's most recent update, do you think you will be given a fair grade this summer?

Yes (344)
34.68%
No (648)
65.32%

Watched Threads

View All