x Turn on thread page Beta
 You are Here: Home

# WJEC Alogrithms question. watch

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.
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?
3. Yes thanks.
When it said recursion all i was thinking was do loops or while loops.
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.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 5, 2018
Today on TSR

### Four things top students are doing

Over the Easter break

### Her parents made her dump me

Poll
Useful resources

Can you help? Study Help unanswered threadsStudy Help rules and posting guidelines

## Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE