experchange > fortran

Abbas Raboonik (11-08-18, 10:59 AM)
Hello forum,

Assume a function is invoked inside a loop within itself. For example,

recursive function sample(a) result(b)
type, intent(in), dimension(:,...,:) :: a
type, allocatable, dimension(:,...,:) :: b
integer i

do i = 1, 10
...

allocate(b(size(a,1) - 1,size(a,1) - 1))

...

... sample(b)

...

deallocate(b)

...

end do

end function sample

My question in particular is, by the time the function is being called at a specific "i", how the compiler preserves its current value for the future time. Does it create a new variable in each time the function is invoked within itself?
Incidentally, is this form equivalent to nesting do loops inside one another for as many iteration as the conditions of the loop imposes?

Many thanks in advance.

Cheers
Wolfgang Kilian (11-08-18, 11:32 AM)
On 08.11.2018 09:59, Abbas Raboonik wrote:
[..]
> end do
> end function sample
> My question in particular is, by the time the function is being called at a specific "i", how the compiler preserves its current value for the future time. Does it create a new variable in each time the function is invoked within itself?


Yes, it creates a new instance of the variable i each time this function
is invoked. The instance within the calling function is not overwritten
by the new instance. (Technically, it is likely that the run-time
system will allocate the new variable on the stack and remove it when
the function evaluation has completed.)

> Incidentally, is this form equivalent to nesting do loops inside one another for as many iteration as the conditions of the loop imposes?


Yes, as long as the algorithm for recursive evaluation is correct.

> Many thanks in advance.
> Cheers


-- Wolfgang
Abbas Raboonik (11-08-18, 11:51 AM)
On Thursday, November 8, 2018 at 8:32:11 PM UTC+11, Wolfgang Kilian wrote:
[..]
> --
> E-mail: firstnameinitial.lastname
> Domain: yahoo


Thanks a lot Wolfgang. So it's hugely counter-efficient then. But I can imagine situations wherein there's no other option at hand but nesting loops.
robin.vowels (11-08-18, 05:15 PM)
On Thursday, November 8, 2018 at 7:59:13 PM UTC+11, Abbas Raboonik wrote:
[..]
> end function sample
> My question in particular is, by the time the function is being called at a specific "i", how the compiler preserves its current value for the future time. Does it create a new variable in each time the function is invoked within itself?
> Incidentally, is this form equivalent to nesting do loops inside one another for as many iteration as the conditions of the loop imposes?


In computers having a stack, calling a procedure recursively is treated
as an ordinary procedure call. Storage is allocated for local variables, etc.

In computers without a stack, a recursive call requires additional
instructions to save the return address at east.

The overheads are small unless the procedure is trivial.
Dominik Gronkiewicz (11-10-18, 04:32 PM)
From what I know, recursion has never been the most CPU efficient way to doanything. Sometimes it just simplifies code a lot (or makes solving a taskpossible at all). It usually pays off for big irregular jobs that can't besimply written in nested loops. And if you have doubts -- just benchmark it and see which solution works best.
Abbas Raboonik (11-11-18, 08:53 AM)
On Sunday, November 11, 2018 at 1:32:14 AM UTC+11, Dominik Gronkiewicz wrote:
> From what I know, recursion has never been the most CPU efficient way to do anything. Sometimes it just simplifies code a lot (or makes solving a task possible at all). It usually pays off for big irregular jobs that can't be simply written in nested loops. And if you have doubts -- just benchmarkit and see which solution works best.


Dominik,

Well put thanks. I investigated my question more and I figured out that recursion is of significant use to mathematicians for proving things by induction, apart from what you laid out regarding the use of recursive functions in situations wherein there's no apparent alternative ways to solve the problem at hand merely by dint of nesting loops. Consider the case of factorial function,

recursive function factorial(n) result(output)
if (n .eq. 1 .or. n .eq. 0) then
output = 1 !the base case, which we assume true
else
output = n * factorial(n-1)
end if
end
Now if we induce the case of n = k + 1 assuming k>1
output = (k + 1) factorial(n)
so that it confirms that factorial(k + 1) = (k + 1) * factorial(k).
Vishnu (11-13-18, 03:51 PM)
@Abbas, Recursions are of import in mathematics, but surely not for the factorial function. In fact, I think it unnecessarily complicates it. Are you saying that there is no alternative to it, other than a recursive function? What about this:

function factorial(n) result(output)
output = 1
do i = 1, n
output = output * i
end do
end function

One of the famous situations where you can't do without it is the Ackerman function:
Abbas Raboonik (11-15-18, 02:07 AM)
On Wednesday, November 14, 2018 at 12:51:43 AM UTC+11, Vishnu wrote:
> @Abbas, Recursions are of import in mathematics, but surely not for the factorial function. In fact, I think it unnecessarily complicates it. Are you saying that there is no alternative to it, other than a recursive function? What about this:
> function factorial(n) result(output)
> output = 1
> do i = 1, n
> output = output * i
> end do
> end function
> One of the famous situations where you can't do without it is the Ackerman function:


Vishnu, yes factorial isn't an archetype of recursive functions. I just wanted to demonstrate what I mean by the role of recursive induction in mathematics. Thanks for your point.
michaelmetcalf (11-15-18, 11:20 AM)
Just for information, the latest SPEC benchmark suite () contains a Fortran program using recursion, 648.exchange2_s, in the CPU2017 Integer Speed set. This means that comparisons in this area are being made.

Regards,

Mike Metcalf
Similar Threads