Printer Friendly

Email

Recursion & Iteration: A piece of code which executes repeatedly based on the different inputs. In general, before solving any large problem first, we need to divide the problem and then you need to solve either using iterative way or recursion way.

Recursion sample:
unsigned long FactorialR(int Num)
{
if (Num == 0)
return(1);
return(Num*FactorialR(Num-1));
}

This function will take 'Num' as parameter and executes the same function till it satisfies exit condition i.e 'Num == 0'.

For ex: If we pass 5 as parameter to this function it will execute as following:

1. Num[5]*Factorial(Num-1)[?] -> 5*? it doesn't return immediately

2. Num[4]*Factorial(Num-1)[?] -> 4*? it doesn't return immediately

3. Num[3]*Factorial(Num-1)[?] -> 3*? it doesn't return immediately

4. Num[2]*Factorial(Num-1)[?] -> 2*? it doesn't return immediately

5. Num[1]*Factorial(Num-1)[?] -> 1*? it doesn't return immediately

After Num == 0, then it will start returning result of processed result of the function in reverse order like following:

1. Num[1]*Factorial(Num-1)[ 1]  -> 1* 1 (1 is returned value of the previous function call)

2. Num[2]*Factorial(Num-1)[ 1]  -> 2* 1 (1 is returned value of the previous function call)

3. Num[3]*Factorial(Num-1)[ 2]  -> 3* 2 (2 is returned value of the previous function call)

4. Num[4]*Factorial(Num-1)[ 6]  -> 4* 6 (6 is returned value of the previous function call)

5. Num[5]*Factorial(Num-1)[24] -> 5*24 (24 is returned value of the previous function call)

Finally, function will return 120 result to the caller.

Iteration sample:

unsigned long FactorialI(int Num)
{
int Result = 1;

for ( ; Num > 0; Num-- )
Result = Result * Num ;

return(Result);
}

This function will take 'Num' as parameter and executes the same code inside the loop till it satisfies exit condition i.e 'Num > 0'.

For ex: If we pass 5 as parameter to this function it will execute as following:

1. Result * Num ->     1*5 =     5 (5 is stored in 'Result' variable)

2. Result * Num ->     5*4 =   20 (20 is stored in 'Result' variable)

3. Result * Num ->   20*3 =   60 (60 is stored in 'Result' variable)

4. Result * Num ->   60*2 = 120 (120 is stored in 'Result' variable)

5. Result * Num -> 120*1 = 120 (120 is stored in 'Result' variable)

Finally, function will return 120 result to the caller.

Code generation by compiler for a function: Any function you write, compiler will generate default prolog and epilog for it. So, it will reserve stack for local variable once it enters the function and while leaving the function, it will restore the old value of registers. Layout will look like following by default:

[Prolog]
[Function Body]
[Epilog]

For example:

[Prolog]
push ebp ; Save ebp
mov ebp, esp ; Set stack frame pointer
sub esp, localbytes ; Allocate space for locals
push <registers> ; Save registers. <registers> will represent list of registers to be saved

[Function Body]

[Epilog]
pop <registers> ; Restore registers. <registers> will represent list of registers to be restored old values
mov esp, ebp ; Restore stack pointer
pop ebp ; Restore ebp
ret ; Return from function


This Epilog and Prolog code generation will vary from compiler to compiler. Microsoft compiler will allow give option to prevent default code generation of Prolog and Epilog for a given function using a keyword called 'naked'. This will help you to write your own custom Prolog and Epilog code.

Calling function: When you call any function, first it will push parameter from right to left and then it will push return address before jumping to function. After completing the execution of function, it will jump back to return address which is stored earlier in stack. Normally it will use instruction 'ret' or 'ret <Num>' where it will transfer control to the address which is found in stack.

For example: TestFunction(10, 30). If you call this function, compiler will generate code like following:

04000000 push 1Eh // 30 == 1Eh
04000002 push 0Ah // 10 == 0Ah
04000004 call TestFunction
04000009 <other instructions>

After executing "call TestFunction". Stack will look like following:


05000005 04  ---          <-----Top of stack
05000004 00     |
05000003 00     |  // 04000009h (Stored reverse and this is implementation specific)
05000002 09  ---
05000001 0Ah  // 10
05000000 1Eh  // 30     <-----Bottom of stack

After completion of function execution, it will transfer control back to caller function. Depends on the calling convention either caller or the calle will clear the stack which is used for parameter pushing.

Difference between Iterative and Recursion method: Take any kind of problem; you can use either Iterative or Recursion method to solve it. If you can solve using iteration method, same problem can be solved with recursion way and vice versa. But, during solving problem you are going to decide based on following factors:

• Does this system have enough stacks?

• Which method takes less code i.e. Iterative or Recursive?

• Is it possible to solve this problem using Iterative method easily?

• Is it possible to solve this problem using Recursion method easily?

• Which method is faster i.e. Iterative or Recursive?

If you use Recursion way, compiler will allocate space for variable after entering function and it de-allocate space in stack while leaving the function automatically. This is achieved using Epilog and Prolog code generated by compiler. Recursion function will take some value as parameters and it will process and returns the result (Check above FactorialR() function and also Prolog, Epilog). All the process result will be stored in stack variables till it returns the final result. In Recursion method Prolog and Epilog plays important roles in getting final output. All of the following 3 will contribute to get final result:
[Prolog] /* This will execute once*/
[Function Body] /* This will execute once*/
[Epilog] /* This will execute once*/

If you use Iterative way, compiler will not generate anything automatic code like prolog or epilog for a loop. You are going to store the result during iterative process (a piece of code which is executing inside loop) in stack variables. Once loop exits it will have some expect result. This iterative method will be in "[Function Body]" (check above compiler code generation for a function). In Iterative method Prolog and Epilog will not play any role in getting complete result, it might just store processing result during loop execution. Only function body will be contributed to get final result:
[Function Body] /* This will execute more then once*/

Recursion to Iteration: During converting in this way, we need to create own stack, this stack will store all (it depends) the variable which is created using Prolog code in recursion method. After we use those stack variable then we need to remove from stack which is like Epilog, de-allocating stack variables.

Iteration to Recursion: During converting in this way, we need to analyze, what does we need to store in stack (Prolog), what does processing code should contain (Function Body), this will generally have the code which is executed inside loop and how does stack cleanup happens (Epilog).

For both conversion example check above sample FactorialI() & FactorialR(). Remember, while solving problem as mentioned above you need to consider factors to identify which method is best to solve this problem or else you might solve the problem but in ugly way.

Above sample FactorialI() & FactorialR() are simple to solve. But, to solve complex problems some are easy to think in recursion way some are easy to think using Iterative way. To convert between these 2 methods, you need to visualize how does compiler generate code for both Recursion and Iterative method which will make more easy for conversion.

For example: You know to solve the problem in recursion way, but in some system where there is less stack you need to maintain your own stack to do the implementation. If you can visualize how compiler does generate code for a function and also if you trace manually, you can convert to manual stack implementation easily.