Rekurencj

Rekurencja, to odwoływanie się funkcji (na przykład obliczającej, wyszukującej itp.) do samej siebie. Działanie rekurencji polega na utworzeniu stosu danych z kolejnych wywołań wchodzących w głąb w kolejności od n do 1. Powstaje stos danych i instrukcji), w których na górze stosu znajdują się dane i instrukcje odpowiadające rekurencji 1. W kolejnym etapie ze stosu są zdejmowane (pobierane) kolejne wywołania od 1 do n.

Rekurencje w przeciwieństwie do iteracji dla tego samego problemu wykonują więcej instrukcji. Ponieważ musza wejść w głąb wywołań- utworzyć stos, a następnie ze stosu zdejmować dane i instrukcje.

Zaletą rekurencji jest czytelność kodu, uproszczenie kodowania złożonych problemów algorytmicznych

Rekurencja na przykładzie silni

Czym jest silnia? Silnia liczby naturalnej n jest iloczynem kolejnych liczb naturalnych od 1 do n. Ogólnie silnię oznacza się symbolem n!. Na przykład silnia liczby 5 oznaczona jest symbolem 5!, a jej wartość wynosi

5!=1⋅2⋅3⋅4⋅5=120

Pamiętaj, silnia 0! wynosi 1

Rekurencyjna definicja silni

Schemat rekurencyjnego wywołania funkcji silni

Źródło Informatyka dla szkół ponadpodstawowych. Zakres podstawowy Klasa III wyd. MiGra

Zadanie

Utwórz aplikację, która obliczy rekurencyjnie i iteracyjnie wartość silni oraz sumy kolejnych liczb naturalnych dla liczby podanej z klawiatury.

Proponowany układ kontrolek

aplikacj aobliczajaca silnie, Visual Studio C#

Label- 1
TextBox- 1
Button- 4

Schemat obliczenia silni metodą rekurencyjną

Kod funkcji obliczającej wartość silni z wykorzystaniem rekurencji

Wskazówka:


long silnia_rekurencyjnie(int n)
{
	if (n == 0)
		return 1;
	else
		return n * silnia_rekurencyjnie(n - 1);
}

Funkcję wywołamy w zdarzeniu Click przycisku button1. Wynik wyślemy na ekran w postaci okna dialogowego

Wskazówka:


private void button1_Click(object sender, EventArgs e)
{
	//rozwiązanie nie zabezpiecza przed błędem konwersji
	int n=Convert.ToInt16(textBox1.Text);
	MessageBox.Show("Silni arekurencyjnie = "
					+ silnia_rekurencyjnie(n).ToString(),
					"Komunikat",
					MessageBoxButtons.OK,
					MessageBoxIcon.Information
					); 
}

Skompiluj program i sprawdź efekt działania.

silnia metodą rekurencyjną, Visual Studio C#

Schemat obliczenia silni metodę iteracyjną

silnia metodą iteracyjną, Visual Studio C#

Kod funkcji obliczającej wartość silni z wykorzystaniem iteracji

Wskazówka:


long silnia_iteracyjnie(int n)
{
	int i = 1;
	long s = 1;
	while (i <= n)
	{
		s = s * i;
		i++;
	}
	return s;
}

Funkcję wywołamy w zdarzeniu Click przycisku button2. Wynik wyślemy na ekran w postaci okna dialogowego

Wskazówka:


private void button2_Click(object sender, EventArgs e)
{
	//rozwiązanie nie zabezpiecza przed błędem konwersji
	int n = Convert.ToInt16(textBox1.Text);
	MessageBox.Show("Silnia iteracyjnie = "
					+ silnia_iteracyjnie(n).ToString(),
					"Komunikat",
					MessageBoxButtons.OK,
					MessageBoxIcon.Information
					);
}

Skompiluj program i sprawdź efekt działania.

Sumowanie rekurencyjne i iteracyjne

Poniżej przykład dwóch metod obliczenia sumy kolejnych liczb naturalnych. Pierwsza funkcja jest rozwiązaniem rekurencyjnym, druga- iteracyjnym. Porównaj złożoność obu metod

Wskazówka:


int suma_rekurencyjnie(int n)
{
	if (n == 0) return 0;
	return n + suma_rekurencyjnie(n - 1);
}

int suma_iteracyjnie(int n)
{
	int s = 0;
	if(n==0) return 0;
	for (int i = 1; i <= n; i++)
		s = s + i;
	return s;
}

Sprawdź jak działają obie metody. Funkcje wywołaj analogicznie jak dla silni. Wykorzystaj klawisze button3 i button4. Poniżej oczekiwany wynik działania aplikacji

suma rekurencyjna i iteracyjna, Visual Studio C#

Pełny kod utworzonej aplikacji

Wskazówka:


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace rekurencja
{
    public partial class Form1 : Form
    {
        long silnia_rekurencyjnie(int n)
        {
            if (n == 0)
                return 1;
            else
                return n * silnia_rekurencyjnie(n - 1);
        }

        long silnia_iteracyjnie(int n)
        {
            int i = 1;
            long s = 1;
            while (i <= n)
            {
                s = s * i;
                i++;
            }
            return s;
        }

        int suma_rekurencyjnie(int n)
        {
            if (n == 0) return 0;
            return n + suma_rekurencyjnie(n - 1);
        }

        int suma_iteracyjnie(int n)
        {
            int s = 0;
            if(n==0) return 0;
            for (int i = 1; i <= n; i++)
                s = s + i;
            return s;
        }

        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            //rozwiązanie nie zabezpiecza przed błędem konwersji
            int n=Convert.ToInt16(textBox1.Text);
            MessageBox.Show("Silnia rekurencyjnie = "
                            + silnia_rekurencyjnie(n).ToString(),
                            "Komunikat",
                            MessageBoxButtons.OK,
                            MessageBoxIcon.Information
                            ); 
        }

        private void button2_Click(object sender, EventArgs e)
        {
            //rozwiązanie nie zabezpiecza przed błędem konwersji
            int n = Convert.ToInt16(textBox1.Text);
            MessageBox.Show("Silnia iteracyjnie = "
                            + silnia_iteracyjnie(n).ToString(),
                            "Komunikat",
                            MessageBoxButtons.OK,
                            MessageBoxIcon.Information
                            );
        }

        private void button6_Click(object sender, EventArgs e)
        {
            //rozwiązanie nie zabezpiecza przed błędem konwersji
            int n = Convert.ToInt16(textBox1.Text);
            MessageBox.Show("Suma rekurencyjnie = "
                            + suma_rekurencyjnie(n).ToString(),
                            "Komunikat",
                            MessageBoxButtons.OK,
                            MessageBoxIcon.Information
                            );
        }

        private void button5_Click(object sender, EventArgs e)
        {
            //rozwiązanie nie zabezpiecza przed błędem konwersji
            int n = Convert.ToInt16(textBox1.Text);
            MessageBox.Show("Suma iteracyjnie = "
                            + suma_iteracyjnie(n).ToString(),
                            "Komunikat",
                            MessageBoxButtons.OK,
                            MessageBoxIcon.Information
                            );
        }
    }
}