Probably a very beginner question, but it's been mind-boggling.
I have an example with the Fibonacci sequence.
fib(int n) {
if (n <= 1) { //Base Case
return n;
}
return fib(n - 1) fib(n - 2)
}
So I mainly have a problem with understanding how the function iterates and it still doesn't make sense, when I print every iteration step by step.
The algorithm itself works, but how does the sequence get smaller over time, so it'll eventually meet the conditions of the base case?
For example if we pass in n=6 the first number should be 9, next step n=11 and from there on it just gets bigger. But the algorithm instead when I print it, counts down from 6-0 and then I get random numbers between 0 and 2 till it gives me the correct number.
CodePudding user response：
When you pass in n=6, your function is called twice, with n=5 and n=4
For n=5, it is called twice with n=4 and n=3
For n=4 it is called twice with n=3 and n=2,
...etc
Evenatually, all calls becomes with n=1 or n=0, in which your first if-statement stops the recursion.
CodePudding user response：
n never changes. It doesn't get smaller. Rather, each call has its own n.
Let's look at a simpler but very similar example.
int fact(int n) {
if (n <= 1) {
return 1;
}
return n * fact(n-1);
}
fact(1)is1. That was pretty easy.fact(2)is2 * fact(1). From above, we know thatfact(1)is1, sofact(2)is2 * 1, which is2.fact(3)is3 * fact(2), which is3 * 2, which is6.fact(4)is4 * fact(3), which is4 * 6, which is24.fact(5)is5 * fact(4), which is5 * 24, which is120.- etc.
Fibonacci is extremely similar.
fib(0)is1fib(1)is1fib(2)isfib(1) fib(0), which is1 1, which is2fib(3)isfib(2) fib(1), which is2 1, which is3fib(4)isfib(3) fib(2), which is3 2, which is5fib(5)isfib(4) fib(3), which is5 3, which is8- etc
This makes a lot more call than the above implies.
fib(5)
= fib(4) fib(3)
= fib(3) fib(2) fib(2) fib(1)
= fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) 1
= fib(1) fib(0) 1 1 1 1 1 1
= 1 1 1 1 1 1 1 1
= 8
That's a total of 15 calls to fib for fib(5)!
fib(0): 1 call.fib(1): 1 call.fib(2): 3 calls.fib(3): 5 calls.fib(4): 9 calls.fib(5): 15 calls.- etc
(This sequence is very similar to the Fibonacci sequence!)
CodePudding user response：
The fundamental characteristic of a recursive function is that it calls itself. Recursive functions do not iterate as you seem to have understood it. Instead, it recurs as in it occurs again and again.
In your fib function, the part that calls itself is in the return.
return fib(n - 1) fib(n - 2)
In this case, it actually calls itself twice. First, with the input variable decreased by 1 fib(n - 1) and second with the input variable decreased by 2 fib(n - 2) and it keeps calling itself until n is less than or equal to 1. Once it reaches that condition, the function starts returning the numbers back. First, it returns 0 and 1 but after that it starts returning the numbers added together. The execution steps are shown in @cptFracassa's answer.
Something to note; if a recursive function does not have a base/exit case then it will just keep calling itself continuously until either you kill the process or something bad happens to the machine. In your case, the base case is the if that finally stops calling itself and just returns a number.
CodePudding user response：
You state that you have printed all the values in order to understand what going on.
I suspect that you have only printed values, without an indication why that value occurs.
Here is a modified code version which tells you a more verbose story of the values.
Note that the program is very forgetful and cannot remeber a value once calculated and used. If the same value is needed again it will cheerfully calculate it again.
#include <stdio.h>
fib(int n){
int retValue=0;
printf("Trying to determine fibonacci at index %d.", n);
if(n<=1){ //Base Case
printf(" Easy, it is %d.\n", n);
return n;
}
printf(" No idea. But I could sum up the fibonaccis at index %d and index %d.\n", n-1, n-2);
retValue= fib(n-1) fib(n-2);
printf("I now know the fibonaccis at index %d and at index %d, their sum is %d.\n", n-1, n-2, retValue);
return retValue;
}
int main()
{
const int TryWith = 6;
printf ("The fibonacci at index %d is %d.\n", TryWith, fib(TryWith));
return 0;
}
The output is:
Trying to determine fibonacci at index 6. No idea. But I could sum up the fibonaccis at index 5 and index 4.
Trying to determine fibonacci at index 5. No idea. But I could sum up the fibonaccis at index 4 and index 3.
Trying to determine fibonacci at index 4. No idea. But I could sum up the fibonaccis at index 3 and index 2.
Trying to determine fibonacci at index 3. No idea. But I could sum up the fibonaccis at index 2 and index 1.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
Trying to determine fibonacci at index 1. Easy, it is 1.
I now know the fibonaccis at index 2 and at index 1, their sum is 2.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
I now know the fibonaccis at index 3 and at index 2, their sum is 3.
Trying to determine fibonacci at index 3. No idea. But I could sum up the fibonaccis at index 2 and index 1.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
Trying to determine fibonacci at index 1. Easy, it is 1.
I now know the fibonaccis at index 2 and at index 1, their sum is 2.
I now know the fibonaccis at index 4 and at index 3, their sum is 5.
Trying to determine fibonacci at index 4. No idea. But I could sum up the fibonaccis at index 3 and index 2.
Trying to determine fibonacci at index 3. No idea. But I could sum up the fibonaccis at index 2 and index 1.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
Trying to determine fibonacci at index 1. Easy, it is 1.
I now know the fibonaccis at index 2 and at index 1, their sum is 2.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
I now know the fibonaccis at index 3 and at index 2, their sum is 3.
I now know the fibonaccis at index 5 and at index 4, their sum is 8.
The fibonacci at index 6 is 8.
CodePudding user response：
One way to understand how a recursive function iterates is to attempt to implement the recursive algorithm using a traditional imperative loop.
A function call is normally explained as an operation that pushes some data onto a call stack, and then the stack frame of reference is adjusted and then the invoked function operates on the parameters on the top of the stack. The return of a function call pops the data off of the call stack, and the function result is returned to the caller at the point of invocation.
A recursive call is simply a function calling itself. To simulate the call using only an imperative loop, we need a stack. Let's first define some stack operations, and what a stack frame looks like.
#define MAX_STACK_SIZE 256
typedef struct {
enum { INIT, ONE, DONE } ra;
int n;
int result;
} frame_type;
#define PUSH(...) stack[head ] = ((frame_type){__VA_ARGS__})
#define POP() stack[--head]
#define TOP() stack[head-1]
#define EMPTY() (head == 0)
ra simulates a return address, which is how a called function knows how to return to the caller. n is the input parameter, and result is a place to store the result of any called functions.
The recursive calls will be simulated with a loop. The CALL() macro shows preserving the proper return address, pushing a new stack frame onto the stack to start a recursive call, and restarting the loop with continue, which starts the function with the new stack frame.
#define CALL(N) \
TOP().ra = top.ra 1; \
PUSH(INIT, (N), 0); \
continue
The RET() macro simulates returning from a recursive call. It pops off the current function call stack frame, and then stashes the computed result into the caller's result variable. The restarting of the loop with continue allows the caller to resume at the proper place after the return of the called function.
#define RET(X) \
POP(); \
TOP().result = (X); \
continue
So now, let's look at what the fib() function might look like using these macros.
A stack and head is defined to give the function an actual stack to manipulate with the macros. And then, there is some bootstrapping code to give stack some starting context for the initial function call.
The while implements the traditional imperative loop that will be used to emulate the recursive iterations. The top is used to retain the current stack frame, and the switch statement is used to jump to the proper return address.
int fib(int n) {
frame_type stack[MAX_STACK_SIZE];
int head = 0;
PUSH(DONE, 0, 0); // Bootstrapping call
PUSH(INIT, n, 0);
while (head > 1) {
frame_type top = TOP();
switch (top.ra) {
case INIT: if (top.n < 2) {
RET(top.n);
} else {
CALL(top.n-1);
case ONE: CALL(top.n-2);
}
case DONE: if (head == 1) break;
RET(top.result);
}
}
POP();
assert(EMPTY());
return stack->result;
}